Codeforces Beta Round #30

Codeforces format というものが何だかよく分かってないので、ルールを一通り眺めてから参戦。

書くだけ・・・だけど、何か罠がありそうだ。
とりあえず X を全探索してやればいいよね。
- 指数だし、-10 .. 10 ぐらいまで調べれば十分かな？
  - ...いやいや、n = 1 のとき X = 1,000 になりうるわけで。
- -1000 .. 1000 まで調べる・・・と、今度はオーバーフローの予感。
n = 1 ならば直接計算して、それ以外は -100 .. 100 で全探索でいいか。
書けた。念入りにテストとかしてみる。
submit. Pretest通った。

これも典型的DPでよさそう。
- dp[i][j] := 的 i が消失した直後で的 j に照準が合っている状態での最大期待値な感じで。
...なんだか実装に手間取る。DP力落ちてるなぁ・・・。
submit. Pretest failed.
・・・あ！入力が時刻の昇順に来るとかどこにも書いてない！罠だ！
- 今更構造体作るのも面倒なので自分でバブルソートを書いてみる。どうせ O(n²) だ。
submit. failed.
...えーと、照準を合わせるときの許容時間は t[i] - t[i-1] じゃなくて t[i] - t[j] だよね。
submit. failed.
...えーと、的 i に照準を合わせた状態で開始するケースを考えてなかったね。
submit. failed.
...えーと、最終的な答えは *max_element(dp[n], dp[n]+n) じゃなくて *max_element(dp[n], dp[n]+n+1) だよね。
- いくらなんでもDPミスりすぎだろ！頭悪すぎる...。
submit. failed.
え、まだバグあるの？もうやだ...。
...
入力読み込む前にソートしてた。これはひどい。
Pretest passed.
- どうにか間に合った・・・。

残り10分ぐらいなので、3問ロックしてHackに挑戦してみたい。
- 誰かのコードopen。
  - え？何この言語見たことない。
  - Delphi とか勘で読めそうな気もするけどしんどいなぁ・・・。なんかコーナーケースも対処してる感じだし。
結局 0 hack で終了。
- SRMのサンプルデータに比べてPretestは厳しいので、なかなか撃墜しづらいのかな。
- もっとPretestを緩くすればいいのにーとか思ったけど、そうすると自分の今日の C なんかは撃墜されてたに違いない。