TopCoder SRM 433 DIV1
ふにゃふにゃ。
Coding Phase
- 250点問題
- 文字列検索。愚直に書くと時間内に終わらない。遅そうなパターンにはアドホックな方法で対策をしたけれど、カバーしきれなかった例があったみたいでテストFailed。文字列のちょっとした性質をひとつ使えば簡単に答えが出せるみたいです。たぶん文字列検索アルゴリズムの定番なところなので、知識不足。
- 500点問題
- xy座標平面上の与えられた領域内で、4つの頂点全てが格子点になっている菱形は何個できるか。
とりあえず全探索したらO(N^6)で出せるのだけどさすがにそれは時間的に無理。いろいろ考えたけど時間内にはわかりませんでした。1点を原点に固定した状態で探索して、何通り平行移動できるか数える、とかの工夫をしたらオーダー下げられるのかかな？
Challenge Phase
250点で全探索してるっぽい人がいたので投げてみたが、失敗。
System-Testing Phase
落ちました。たぶん時間オーバーだろう。
結果
| Level | Status | Coding Time | Score |
|---|---|---|---|
| 250 | Failed System Test | 30分くらい | 0.0 |
| 500 | Opened | 40分くらい | 0.0 |
| 1000 | Unopened | - | 0.0 |
チャレンジ1回失敗 -25
スコア -25.0 / 691人中620位 / レーティング 1707→1523
ぎりぎり黄色圏内。
