Google Code Jam 2012 Round 1A
A-small, Bを正解。1251位でした。
A-largeはほぼ解けていたのですが、ケアレスミスで落としてしまいました。
合っていれば余裕で通過だったのですが…Round 1Bをがんばります。
A. Password Problem
指示通り計算するだけです。
ただし、backspaceの場合を素直に実装するとO(n^2)になり、
ワーストケースで100000^2なので間に合いません。
これに気付かずlargeを実行してしまい、慌てて直したのですが配列のindexがひとつずれていてwrong。残念な結果でした。
バグ修正後の、largeが通るコードです。
GCJ 2012 Round 1A - A. Password Problem · GitHub
B. Kingdom Rush
サンプルを眺めてると、Greedyでいけることに気付きます。
下記の繰り返しで解けます。
- 現状で、2-starでクリアできるレベルを選びます。複数ある場合はどれでもかまいません。
- 現状で、1-starでクリアできるレベルを選びます。複数ある場合は、2-starの条件が最も厳しいものを選びます。
- 例: サンプルのCase #4で、0 5, 0 1の2択になったら、0 5を先にクリアします。
- そうすることで、次に0 1の1-starを飛ばして2-starに挑戦でき、1回節約できます。
- どちらも不可能で、未クリアのレベルが残っている場合はToo Badです。
サンプルがヒントになっているあたり親切ですね。
GCJ 2012 Round 1A - B. Kingdom Rush · GitHub
C. Cruise Control
レーンチェンジが必要なのは、前後の車との間隔が0mになった瞬間だけです。たぶん。
事前にレーンチェンジしないと間に合わない場合はないと思います。
それなら、その瞬間の時刻を2分探索で求めればいいのかな。
…くらいまで考えたところで気力と時間が尽きてしまいました。