Codeforces Round #23

Codeforces 参加記録

Result

139 位 2AC penalty 74 / 00:03 / 00:31(2WA) / (3WA) / - / -


orzorz

1664->1660

A. You're Given a String...

問題

英小文字からなる100字以下の文字列が与えられる。
この文字列の連続する部分文字列で、元の文字列に二回以上出現する（一部重複してもよい）ようなもののうち最長ものの長さを求めよ。

試行錯誤

むず……かしくないか。長さ100なので連続する文字列は5000通りくらい。
全通りについて2度以上出現するか調べればいい。


AC.

B. Party

問題

パーティにN人が来る。

  • 友達が一人もいない人が帰る。
  • 残っている人の中にいる友達が1人だけの人が帰る。
  • 残っている人の中にいる友達が2人だけの人が帰る。

…

  • 残っている人の中にいる友達がN-1人だけの人が帰る。

このとき、パーティの最後まで残っていられる最大の人数を求めよ。

試行錯誤

うん？？問題の意味が全くわからない。
読み直す。やっぱわからない。


友達が0人,1人,2人...を取り除く……って誰も居なくなるんじゃないのかそれ。


うーん。C,D,Eを解いてる人いない。
問題見てもなんかグロい。もうちょっとこれ考えてみるか。


友達が0人の人を取り除いて、友達が1人の人は残って、友達が2人の人は居なくなって……ってことか？
いやそれだとサンプルは2人が答えになるはず。


あ、「まだパーティに残ってる人」の中の友達の数を数えるってことか。


えっと、どうしたらいいんだろう。図を描く。
3人のとき1人……残るのがn人として、その人たちが友達同士だとするとその人たちの友達の数はn-1人。
んで、「残りの人たち」の友達の数がn-1で、n-1人友達がいる人達が一気にいなくなるとき、「残りの人たち」が丁度全部消えたらいい。


なるほど、よくわからん。nの半分くらいか？5のときの答えって2だよな？
3はつくれなさそう（←ぼけてる）


n/2にして送信。WA.
あ、1人と2人の場合コーナーケースで0だ。訂正。送信。WA.


あっれー。2WAってやばいぞ。
「残りの人たち」はn-1本のエッジをもってて、んで「最後に残る予定のn人」にその人たち同士以外で、それぞれ1本以上のエッジを入れることが必要。


ってことは他に2人いればいいだけか。
送信。AC.


ハマりすぎorz

C. Oranges and Apples

問題

2N-1個の箱にりんごとオレンジが入っている。
N個の箱を選び、その中に入っているオレンジの数の和を全体のオレンジの数の半分以上に、りんごの数の和を全体のりんごの数の半分以上にしたい。


そのような箱の選び方があるとき"YES"を出力し、選ぶ箱の番号をスペースで区切って出力せよ。
そのような選び方が存在しないときは"NO"を出力し、次の行は空行を出力せよ。


N≦10^5であり、それぞれの箱の中に入っているオレンジの数、りんごの数はそれぞれ10^9個以下である。

試行錯誤

りんごとか怖い。


えーと、一見するとナップサックっぽい感じなんだけど、果物の数が10^14なんだよな。
これじゃDPはむりげ？NP完全じゃねーのかよこれ。
とすると数学的に綺麗な解法がある感じ。


2N-1からN個選ぶってのがなんかそんな雰囲気だなあ……
考えてみるがよくわからない。
status見てみる。ACの人の実行時間は200msとか300msとか。


ソートしかしてなくてグリーディーみたいな感じの時間だろこれ！
えーと、N=3くらいにして色々考える。
"NO"の場合つくってみるか。


りんごが3 3 3 0 0で
オレンジが0 0 0 3 3とか。（←明らかにボケている）
うーん、小さいほうから取るとか何とかはこういう例があるから無理ぽい？


眠気やばい、、、コンテストまだ1時間くらいあるよ。
ベッドで考えよう。
えーと？？あれ、
りんごが3 3 3 0 0で
オレンジが0 0 0 3 3の場合って真ん中の3つの箱取ればいいんじゃん。
あれーじゃあNOの場合ってどんなだ。


そもそも選び方はどういう感じなんだろう。

  • ソートして片方の果物の多い順に適当にとる。片方の果物が満たされたら残りの果物が多い順にとる？
  • Oが1番多い箱、Aが1番多い箱を選ぶ、Oが2番目に多い箱、Aが2番目に多い箱を選ぶ……OがN/2番目に多い箱、AがN/2番目に多い箱を選ぶ、みたいにとる？
  • 合計の個数が多い箱からとる？
  • それぞれの果物の全体に占める割合の和が多い順に箱を取る？

どれもダメそう。
時間もうない。最後ので適当に書いてsubmitしてみるか。
PE.

PE？？？？意味わからん。
送りなおす。PE.

なんでPE？？？？改行とかフォーマットとか間違ってないよな。

D

グロそうだったのでちゃんと読んでない。

E

グロ（ｒｙみてない。