Google Code Jam 2011 Round 1C
今年も参加してます。1B がさっぱりだったので，年々レベル上がってるし今年は無理かなと思いましたが，どうにか通りました。
ちなみに submit して通ったコードは http://www.go-hero.net/jam/11/name/k.kojima から落とせます。
経過
開始直後，なぜか問題文に飛ぼうとするとエラーが出たりして，サインインし直したりしていたら数分のロス。
気を取り直して問題を見る。でもその前に配点をチェック。10 10 12 25 8 35 なので，とりあえず A を通して C small に行って，C large ができそうならやって，それから B かなあという感じの方針をなんとなく考えました。
でとりあえず問題文を読む。まずは A から。これはいかにも貪欲っぽいし上限小さいし A だし，素直にやれば通るんじゃないかな，ということでとりあえず深く考えずに書く。GCJ は WA のペナルティも軽いのであまり気にしない。
たぶん五分かそこらで適当に書いたら通りました。Common Lisp です。submission time は small 12m 43s, large 13m 27s となっています。
A が無事終ったので (本当は large が無事かどうかはわからないけど終わるまでわからないので気にしないで) 次に，C をやりました。その前に B をちらりと見たかもしれませんが忘れました。large は配点 35 なのですぐには解けないだろうということと，C small を早く通しておけばそれだけで 1000 位以内に入れる可能性があると思って，まずは small だけ解くつもりでいました。
small の上限を見たらたいしたことなかったので，なにも考えずに総当たりでやりました。一応 clisp より速そうな Java で書きましたけど，三重ループで外から 40, 100, 10000 なので clisp でもバイトコンパイルすれば平気だったんだと思います。試してませんけど。
で，C のコード自体はすぐ書けたんですけど (first attempt の submission time が 19m 00s となってるので問題文読み始めてからで五分ぐらい) なんか Incorrect が返ってきました。こんなもの間違えようがないんだけどなあ，としばらく悩んでましたが，解がない場合の出力の "NO" が "No" になってました。ついでにそれを直した後コンパイルし忘れてもう一回 Incorrect を頂きました。submission time は 19m 00s, 22m 58s, 26m 05s なのでここで七分ほど無駄にしたことになります。
それから B に移ってしばらく悩む。まず問題文の理解に時間がかかりました。booster は船にあるもんだと思ったら，星にあるとは。
一応内容は理解して，なんとなく解けそうな気はするんだけどいまいちすっきり整理できない感じで，紙にいろいろ書いたりコード書いて sample 合わないなーとかやってました。とりあえず small だけなんとかしようかと思って，0 <= L <= 2 なので booster を置く場所を全通り試せばいいのではないかと思いました。これだと 1000^3 ぐらいのループを一つのテストケースごとに回すので，もしかしたら厳しいかもしれない。でもとりあえず Java で書いてみよう。という感じで。
しばらくコード書いてたら，booster が完成する時刻決まってるんだから二つ目のは完成する時刻以降に着く星のどれかに置くことになると気付く。じゃあ，その中で次の星までの距離が一番長いところに置けばいいよね。これでループが一つ減ったので安心。ということで submit してみたら Incorrect (これを投げた時刻が 1h 24m 11s だったそうです)。
何がおかしかったかというと
...
long ans = Long.MAX_VALUE;
if (L == 0) {
for (int i = 0; i < N; i++) ans += a[i%C];
ans *= 2;
} else if (L == 1) {
...
ans = Math.min(ans, tab[N]);
} else if (L == 2) {
...
ans = Math.min(ans, tab[N]);
}
System.out.println(ans);
...みたいになってて，L==0 だったときの節で ans の初期値が 0 のつもりになってておかしい。ここの分岐は後から追加したので，見落としたんですね。
ということでこんなふうに直しました。(1h 32m 27s)
...
long ans = Long.MAX_VALUE;
if (L == 0) {
ans = 0;
for (int i = 0; i < N; i++) ans += a[i%C];
} else if (L == 1) {
...なんで後ろの二倍する部分を消しちゃったのか知りませんが。
これはさすがにすぐ気付いたので修正しましたが，それでもやっぱり Incorrect (1h 33m 25s) だったり。
結局何だったかというと，「booster 完成後の中で距離が最も長いところ」を計算するときに添え字がひとつずれてて，完成する直前のところも入っていたのでした。最終的に通ったのが 1h 37m 54s で，この問題もつまらないミスで時間を無駄に使いました。
それからしばらく C large 解けるかなー，とか計算していたんですが，どうも方針が見えないのと順位がだんだん落ちてきてこのままでは 1000 以内に入るかどうか怪しい気がしてきたので，B large を考えてみることに。
で，落ち着いて考えてみれば何ということもない問題で，少し見方を変えればすごくシンプルな話なのでした。最初は「ここに booster を置くと何時間かかるか」と考えていたんですが，そうではなくて「ここに booster を置くと何時間節約できるか」を考えればよいのでした。まあ論理的には同じといえば同じなんですけど。そうすると置く場所ごとに節約できる時間はすぐ計算できて，それを大きいほうから L 個とって足したものが節約できる時間の最大値。これを booster のないときにかかる時間から引いたら答えが出る。
で B large のコード書いて，すでに通って正しいとわかっている small の input を食わせて diff をとりながらデバッグして submit。small と large を別々に解くと，こういうことができるのですね。
残りは C large しかやることがないので考えてましたが，いまいち自信のもてない方針がおぼろげに浮かんでくるのみでした。それでもとりあえず実装してみようかと思ったけど時間足りなかったのでそのまま終了。
反省点
C-small 二つ目のコンパイル忘れ Incorrect は，適当なスクリプトでも書いておけば防げたはず。面倒臭がらずに書きましょう。
B-small の添え字のずれは，同じ問題の他のところでも似たようなミスをしてかなり時間を食っています。だいぶ混乱していたんだろうなあとは思いますが，配列の添え字の意味ははっきりさせて，ループに使う変数の意味付けもそれと一貫性ももたせるべきだということでしょう。
あと今回は関係ありませんが添え字のずれと似たような話で，上限・下限が exclusive か inclusive かで混乱やミスをすることがあるので，こういうのも自分の中で常にこうする，という原則を設けておいたほうがいいんだろうと思います。「俺は上限を常に exclusive にするぞ」と決めたら，問題文に "n, inclusive" と書いてあるときには int n = nextInt()+1; にするぐらいのつもりで。
