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でいけることに気付きます。

下記の繰り返しで解けます。

  1. 現状で、2-starでクリアできるレベルを選びます。複数ある場合はどれでもかまいません。
  2. 現状で、1-starでクリアできるレベルを選びます。複数ある場合は、2-starの条件が最も厳しいものを選びます。
    • 例: サンプルのCase #4で、0 5, 0 1の2択になったら、0 5を先にクリアします。
    • そうすることで、次に0 1の1-starを飛ばして2-starに挑戦でき、1回節約できます。
  3. どちらも不可能で、未クリアのレベルが残っている場合はToo Badです。

サンプルがヒントになっているあたり親切ですね。
GCJ 2012 Round 1A - B. Kingdom Rush · GitHub

C. Cruise Control

レーンチェンジが必要なのは、前後の車との間隔が0mになった瞬間だけです。たぶん。
事前にレーンチェンジしないと間に合わない場合はないと思います。

それなら、その瞬間の時刻を2分探索で求めればいいのかな。
…くらいまで考えたところで気力と時間が尽きてしまいました。