Google Code Jam Round 1A, 1C

Contest

頭が弱すぎる結果に。

Round 1A

寝過ごした・・・。1時間遅れて参戦。

Problem A: Multi-base happiness

とりあえず全探索。バグを入れつつ1時間かけて書いた。
100,000まで探索してsmallは通った。が、largeの最悪ケースを入れると出てこない。10,000,000まで探索するようにしたら今度は終わらない。
数学ゲーか。とりあえず放置。

Problem B: Crossing the Road

問題文が長かったので放置。残り時間も少ないし。

Problem C: Collecting Cards

取得済みのカードの数と未取得のカードの数でDP？しかし、どう漸化式を立てたものか・・・。
頭が回らない。そして時間切れ。

反省会

9点では通るはすがございません。
Aは全探索で間に合うのか・・・。見直してみると、私のコードは無駄だらけでした。

Round 1C

18:00から。準備を整えて参戦。

Problem A: All Your Base
  • 数字とアルファベットで表される数が与えられる。が、何進数なのかも、どの文字がどの数に対応しているのかも分からない。適当に解釈して得られる数のうち最も小さいものを答えよ。

与えられた文字の種類から何進数か求めて、上の桁から小さい数を割り当てていくだけ。ただし、0から始まってはならないので最上位桁は1に固定する。
1進数を作ってしまってWAったけど通りました。

Problem B: Center of Mass
  • N個の等速直線運動をする点が与えられる。これらの重心が原点にもっとも近付くのは何時か、その時刻と距離を求めよ。

凸関数だと決め付けて三分探索。WA。精度の問題かと思ってちまちま改良したけどやっぱり駄目でした。
三分探索は何度か書いたことがあるのだけど、Sampleはいつも合うのに一度もAcceptをもらったことがない。いったい何がいけないんだろう・・・。
とりあえず放置してCへ。

Problem C: Bribe the Prisoners
  • 一直線に並んだ独房に囚人が収監されている。一人出獄させるたびに、その両隣の連続した(まだ囚人が残っている)独房のグループに1回ずつ賄賂を渡さなければならない。特定の囚人たちを出獄させるときに、どのような順番で出獄させれば賄賂を渡す回数が最小になるか？

なんとなく、真ん中の方にいる囚人から出獄させていくGreedyでどうにかなりそうな気がしたので書いてみる。サンプルは合ったけど、やっぱりWA。
真面目に考えてみよう。とりあえず正しい入出力セットが欲しかったのでsmallだけ全探索で解いてみる。Correct.
largeは・・・範囲DPか。何故か知らないけど苦手なんだよなぁ、と思いながら書いた。バグった。
残り15分。気分転換にBをやり直してみよう。

Problem B: Center of Mass (retry)

どれかの点がもっとも原点に近付いたときしか最適解になりえないのではと思って、各点の最接近時刻を三分探索。
むしろ正解から遠ざかった。残り2分。あきらめた。

反省会

38点で893位。largeのテスト前は1,080位ぐらいだったので、かなり崖っぷちでした。去年よりもずっと順位が落ちています。
Bは、重心が動かないときに時刻を0としていなかったのがWAの原因でした。詰めが甘い。

追記

小一時間格闘した挙句、Cも通った。やっぱり頭が足りてない。