Codeforces Beta Round #66

解き方の大筋は分かるのに、なぜか test に通らない、なぜか hack されるという
グダグダ回になってしまった。後で確認してみると、どれもこれも場合分けの見落とし
があった。うーむ。

A. The Elder Trolls IV: Oblivon

方針

むむむ……A問題にしては難しい。場合分けがすごく大変そう。後回し。

B. Need For Brake

方針

まず、順位にソートしてみる。

順位を最適化するには、本人に最大得点を与えて、残りは点が低い順に大きい点を与えればよい。

順位を最悪化(?)にするには、本人に点を与えず、残りは点が高い順にさらに点を与えればよい。(←間違い!)

実装

どうコードに落とすか苦しむ。例えば、最悪化するとき、本人に点を与えたくないが、全員に点が入る場合は、本人には最低点を与えないといけない。こういう例外の処理がごちゃごちゃして、なかなか pretest に通らない。

C. LionAge II

方針

これはDPだ。[これまでに確定した文字数][変更した文字数][直前の値] を状態として、それまでのベストスコアを記録すればいい。

実装

DPだし、Cで書いたほうがいいんだろうけど、<del datetime="2011-04-20T23:29:54+09:00">"文字列 数字" ってのが cin では取り込みにくいんだよなぁ。なんで改行しといてくれないんだろう…… (←scanf すればいいのに、気がつかない)</del> 4/11追記: 普通に、cin >> str >> k みたいにできる。cin は空白や改行を区切りとみなす。

かといって、Ruby だと、多次元配列の初期化がすごく面倒……

苦しみつつ書く。pretest 通った。提出。

A に戻る

方針

相加相乗平均の不等式の等式条件を考えると、切断は各方向に
なるべく均等に分配したほうがいいことが分かる。

実装

k を三等分して分配。ここで残りが出るということは、x,y,zのいずれかが3/kより小さいということなので(←誤り!)、残ったものを余裕のある2つに分配。さらに余ったら、1つに分配……みたいなコードを書く。pretest 通った。提出

B に戻る

Bに戻ってまもなく、Cを撃墜される。残り15分だし、やる気がなくなって離脱。

結果

全部落ちる。1734→1639と暴落。紫から青に。

考察

A は、「k を三等分して分配。ここで残りが出るということは、x,y,zのいずれかが3/kより小さいということなので」というのが誤りだった。x, y, zも余裕あるのに、k = 2 となっているかもしれない。

C は、k = 0 のコーナケースで落ちる。直したが、TLE。計算量 100 * 100 * 26 * 26 のはずなんだけど、Ruby だと無理なのか?

B は、得点が揃ってしまう場合に、自分より名前が後ろの人に点を配ったほうが、順位を最悪化できることを考えていなかった。

Topcoder SRM 502

時間ができたので、いつもと違うPCで急遽参加。各種プラグインなどを、直前5分で導入する。

DIV1 250 TheLotteryBothDivs

方針

suffix ということは頭にあったのだが、なぜか prefix の絵を図を書いて考えてしまった。
00, 001, 004 というのがあれば、最初の 00 だけで決まってしまい、残りの7桁は何でもOK。つまり、001, 004 は無視できる。だから、ソートした上で、頭が共通のやつを捨てればよい。

実装

なんか合わない。あ、suffix だから、文字列を reverse してからソートしないとダメじゃないか! STL には reverse がないので、自分で書く……

できた。提出。時間かかりすぎ。144点。

DIV1 500 TheProgrammingContestDivOne

方針

greedy? 単位時間あたりのポイントが高いやつからとか……ああ、無理だ。となると、問題サイズ的および内容的に DP が怪しいけど、これは取っていく順序が関係するからなぁ。bit DP は N = 50 で無理だし、うーん……

実装

とりあえず幅優先探索してみる。テストケース通る。

もちろん、大きなケースでは返ってこないので、時間ごとに最高点をメモしておいて、どんどん枝狩りしたらどうなんだろう? 

あ、メモの更新だけで時間がかかりすぎだ。t = 3 で得点 10000 だったら、t = 3 から 100000 まで全部更新しないといけない。これは大変すぎる。BIT 的なものを使ったらよいかもしれないけど、実装する時間がない。100 単位時間ごとに best を記録したらどうなんだろう……。自分の作ったでかいケース(最大ではないけど)がTLEしなくなった。提出。

結果

250 通る。500 は、TLE 以前に WA する。100単位時間ごとに best を記録する部分が無茶苦茶だった。

考察

250は、なんで「prefix でも suffix でも対称だから同じだろう」って思い込んだんだろう…… そもそも、prefix の図を描いて考えているのがいけない。途中で面倒がらずに suffix の絵に書きなおすべきだった。

500は、ソートしてからDPらしいけど、ソートの仕方はまだ理解していない。「たくさんある中から選んで、しかも順番を考える」という探索の場合、そのままやると階乗になるんだけど、実は順番を固定できてDPになるというパターン(組み合わせと、並び方の分離)は、時々見かけるなぁ。解けないけど