TopCoder Open 2010 Qualification Round 2

QR3は授業と重なってるので、ここで通らなかったら大変残念なことになるのだけど...!

濃厚に匂い立つある最大流...!
...
...最大流？
そもそも「どのマスの8近傍にも、? はたかだか1個しかありません」って？
...
あー。
2つ以上の ? と接していないってことは、各 ? はそれぞれ独立に決めていいってことだよね。
- 500なのにこんな簡単でいいのか？
  - いいよね。きっと。
? の周り 3x3 は両方試して大きな方をとる。それ以外はそのまま。さぁ実装だ。
...
...
できた。やっぱり合わない。
- 3x3を切り出して?を書き換えて関数に放り込んでたけど、5x5を切り出さないと端のセルの生存判定できないよね。修正。
まだまだ合わない。
- ? から遠いセルの次の状態求めてない！アホだ！
sample 3 以外出てきた。それってどんなケースだ？
- 「外側のマスも1になるかもよ」ってご丁寧にも問題文に書いてある！
出てきた。
sample親切だし、後はsubmitしてからデバッグしよう。ポチっとな。
小さいケース -> 出てる
大きいケース -> よくわからないけどとりあえず落ちない
端に ? があるケース -> 出てる
次行こう。

文字列 text と、文字列集合 words が与えられます
textの部分列が words[i] になるような場所に、words[i] を重ねられます
- textの同じ文字の上に複数の words を重ねてはいけません
- 同じ words[i] を何度も使ってもOK
(連続して重なっている text のもっとも長い部分の長さ)² - (全く重なっていない部分の文字数) が得点です
最大の得点は？

どうせ15分じゃ解けないだろうし、撃墜ケースでも作るかと思って開いてみる。
- 1000が自分に解けるほど簡単なはずがないだろうし、これもどうせ重み付き最大マッチングとかだったりするんじゃね？
それはそうと撃墜ポイントだ。
- オーバーフローしそうな問題ではないなぁ。
- 他に撃墜ポイントも見当たらない。
...
...することがなくなってしまった。
- 今更500もチェックするようなケースがない。
真面目に1000を考えよう。
...
...DPじゃね？
- dp[今までに見た文字数][末尾の連続して重なってる文字数][使ったwordsの種類数] = 得点
- みたいな感じで。
...簡単だなぁ。
- でもさすがに3分で書ける気はしない...。
上のDPをそのまま書くとMLEなので、配列2つで頑張らないといけない。という撃墜ケースだけで満足しておこう。

1000を出している人が2人。片方は自分の考えと同じっぽくて、もう片方は結構違うっぽい。
- これは違う方をランダム爆撃するしかないね！
- 失敗...
  - 結局違うほうがSystem Testに通って、自分のと同じ(っぽい)方がSystem Testに落ちました。そんなぁ。
他にはchallengeできずに終了。

oox -25.0 470.94 1516 -> 1566
- 初めて500を通した。やったー。
  - まぁ今回の500は250と言っても差し支えない難易度だったけど。
今日は500を開かずに1000から行くべきだったなぁ。
- いやいや、まずは500をきっちり解けるようにならなくては。