スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Codeforces Beta Round #23

JST 07/10 00:00~02:00 に行われた codeforces beta round 第23回 の記録です。

Tags : プログラミング Codeforces 未解決

[ 問題 ]
今回の問題セットはこんな感じでした。

A. You're Given a String...
100文字以下の文字列が与えられるので、その文字列中に少なくとも2回登場する部分列の中で長さ最大のものを求める。
例)
  trickortreattr
  aieeeeeeeee
  qwertyなし

B. Party
n人がパーティーに参加した。

まず、『今パーティーに参加している人の中に友人が1人もいない人』は帰った。
次に、『今パーティーに参加している人の中に友人がちょうど1人だけいる人』は帰った。
次に、『今パーティーに参加している人の中に友人がちょうど2人だけいる人』は帰った。
・・・
最後に、『今パーティーに参加している人の中に友人がちょうどn-1人だけいる人』は帰った。

さて、今パーティーに参加している人は最大で何人いると考えられるか?
(つまり、誰と誰が友人だという組み合わせは色々考えられるが、ある組み合わせのときには最後まで残る人数が最大になる。そのときの人数を求めるということ)

なお、(問題文には書かれていないが)aがbの友人であれば、bがaの友人であるとしていい。
(つまり、無向グラフを考えればいい)

C. Oranges and Apples
2N-1個の箱それぞれに、りんごとみかんがいくつかずつ入っている。
それぞれの箱に入っているりんごとみかんの数が与えられる。
この中から、りんごとみかんのどちらも全体の半数以上含まれるようにN個の箱を選ぶことができるか?
できるなら、具体的な箱の番号も答える。

D. Tetragon
R2の3点(各座標は0以上10以下の整数)が与えられる。
3辺の長さが等しい四角形で、等しい3辺の中点が与えられた点に一致するような凸四角形は存在するか?
存在する場合は具体的に凸四角形を1つ再現する。

E. Tree
木(閉路を持たないグラフ)が与えられる。
木の頂点数nはn≦700をみたし、辺の数はn-1本である。

この木から、いくつかの辺(0本でもいい)を取り除いて、『"各連結成分の頂点数"の積』が最大になるようにしたい。
『"各連結成分の頂点数"の積』の最大値を求める。


[ 解答 ]
言語は C++。includeとusingは省略。

A.
int main()
{
string str; cin>>str;
int len=str.length();

for(int l=len;l>=1;l--){
for(int i=0;i+l<=len;i++){
for(int j=i+1;j+l<=len;j++){
if(str.substr(i,l)==str.substr(j,l)){
cout<<l;
return 0;
}
}
}
}

cout<<0;
return 0;
}

文字数の上限Nがたった100なので、何も考えずに全通り調べればいい。O(N4)?
ノーミスAC。

B.
int main()
{
int t,n; scanf("%d",&t);
while(t--){
scanf("%d",&n);
if(n==1) printf("0\n");
else printf("%d\n",n-2);
}
return 0;
}

実は数学の問題。
n=5くらいまでを例示して考えてみるとわかった。
答えは max( 0, n-2 ).
ノーミスAC。

証明っぽいもの

 n=1のとき、答え0は自明。n≧2を考える。

 ○まず、n-2人が残るような友人の組み合わせがあることを示す。

  (説明のため、)n人の参加者に1,2,…,nと番号をつける。
  ---------------------------------
  ・1~n-2番の人は、すべて互いに友人である。
  ・n-1番の人と1番の人は友人である。
  ・n-1番の人と2番の人は友人である。
  ・……
  ・n-1番の人とn-2番の人は友人である。
  ・n番の人と1番の人は友人である。
  ・n番の人と2番の人は友人である。
  ・……
  ・n番の人とn-2番の人は友人である。
  ---------------------------------
  このような組み合わせのときは、パーティーに最後まで残っているのはn-2人となる。
  なぜなら、n-1番とn番の人は友人がn-2人いるので帰ってしまうが、それによって1~n番の人は友人がn-3人しかいなくなるので帰らない。

 ○次に、n-1人が残るような組み合わせが存在しないことを示す。

  そのような組み合わせが存在すると仮定する。

  すると、
  『ある1人(Aとする)が先に帰ることで、他のn-1人が最後まで残る』というシナリオになるはず。
  (そうでないと、n人全員が一斉に帰るか、2人以上が帰ってしまう)

  ところが、
  『Aが先に帰ることで、他のn-1人が最後まで残る』
  ということは、Aは他のn-1人全員と友人である必要がある。
  (そうでないと、他のn-1人の友人数の減少に干渉できない)

  しかし、Aは他のn-1人全員と友人だから、Aだけが先に帰ることはできない。
  ゆえに矛盾。
  したがって、背理法より、n-1人が最後まで残る組み合わせは存在しない。

 ○n人が残るような組み合わせが存在しないことは明らか。(必ず誰かは帰る)

 ○以上より、最後まで残る人数は、最大でn-2人。



C. (時間外) (7/12追記)
#define pii     pair<int,int>
#define APPLE first.first
#define ORANGE first.second
#define ORDER second

int main()
{
int t,n; cin>>t;

while(t--){
cin>>n;
vector< pair<pii,int> > fruit(2*n-1); // <apple,orange>,order

long long osum=0; // the number of oranges
for(int i=0;i<2*n-1;++i){
scanf("%d%d",&(fruit[i].APPLE),&(fruit[i].ORANGE));
osum+=fruit[i].ORANGE;
fruit[i].ORDER=i+1;
}

sort(fruit.begin(),fruit.end());

long long psum=0; // partial sum (odd boxes)
for(int i=0;i<2*n-1;i+=2) psum+=fruit[i].ORANGE;

puts("YES");
if((psum<<1)>=osum){
for(int i=0;i<2*n-1;i+=2){
if(i!=0) putchar(' ');
printf("%d",fruit[i].ORDER);
}
}
else{
for(int i=1;i<2*n-1;i+=2){
if(i!=0) putchar(' ');
printf("%d",fruit[i].ORDER);
}
printf(" %d",fruit[2*n-2].ORDER);
}
putchar('\n');
}

return 0;
}

解き方がわからなかったので、adamax氏のtutorialモロパクリ参考にして組みました。
実は、NOになるケースなんてなかったのね。

以下、アルゴリズムの概略。和訳版はまだないと思うので一応書いとく。
1. りんごの数でソート
2-1. 奇数番の箱に入っているみかんの総数みかんの総数の半分以上なら、奇数番の箱(ちょうどN個ある)の番号を出力する
2-2. 偶数番の箱に入っているみかんの総数みかんの総数の半分以上なら、偶数番の箱と2N-1番の箱の番号を出力する

このアルゴリズムで、必ず、題意をみたす箱の組が得られることは簡単に示すことができる。

 みかんの数が題意をみたすことは、2-1, 2-2 の選び方から明らか。
 りんごの数が題意をみたすことを示そう。

 [ 2-1 の選び方のとき ]
   S := a1 + a2 + … + a2N-2 + a2N-1
   S' := a1 + a3 + … + a2N-3 + a2N-1
    ( 0 ≦ a1 ≦ a2 ≦ … ≦ a2N-1 )
  として、2S'≧S を示せばいい。

  これは
   2S'
   = 2a1 + 2a3 + … + 2a2N-3 + 2a2N-1
   ≧ a1 + a1 + a2 + … + a2N-2 + a2N-1
   ≧ a1 + a2 + … + a2N-2 + a2N-1
   = S
  よりわかる。

 [ 2-2 の選び方のとき ]
  多分、同じ感じで示せる。(やってないけど)



D.


A,Bを解いた後はずっとDと格闘すれども、結局解けず。

E.


競技中には問題も読めてない。


今回はA,Bの2問解けて
ratingは13511533
に戻った♪
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。