Q. 競プロ初心者から初級者になった虫ってな～んだ？
AOJ 1126 The Secret Number
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1126
見た目に反してかなり難しい。長時間詰まってしまった。
「一度通ったことを始点にすることはないだろう」からDPを想定するのだが、普通この状況はdfs/bfsでやってしまいがち。それをすると空間計算量O((HW)!)なので詰まる。DPをするとO(HW)。腹立つけどいい問題ではある。
AC TDPC I イウィ
I: イウィ - Typical DP Contest | AtCoder
未証明の部分を 赤字 で書いています。
区間DP。dp[i][j]:=s[i]からs[j-1]までの区間で最適に操作したときの操作後の文字列 とする。あとはiからj-1までの間それぞれ区切る部分を探して（kとする）dp[i][k]+dp[k][j]の長さが最小となるkを探し出せば良いいたって普通の区間DPだが、普通にやると頭が爆発してしまう。
もしもdp[i][k]とdp[k][j]がきっちり最適に操作した後の文字列を表しているならば、 これらをつなげたときに新しく消せる"iwi"はたかだかひとつしかない 。かつそのひとつだけ消せる"iwi"はつなぎ目にまたがるようにして存在する。そして結合を行った後の 最適な文字列は各i, jについて一意に定まる 。
上記の厳密な証明を募集しています。
これらが何となく分かりさえすれば出せば通る問題だが、REが発生した。おそらく要素外参照なので適当に最大ケースを複数生成してローカルでテストしても異常なし。コードテスト機能を使って検証したところ、VCはbasic_string::eraseのout_of_range例外をコンパイル時点で回避することが分かった。お前マジでどういう構造してんの。VCにはビックリドッキリメカが満載だ。
AOJ 2232 Ennichi
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2232
再AC。Nキチくんが詰まっていたのを自分が雑に通した問題。当時より苦労したが、まあ、はい。
落ちものパズルゲームの実装において必ず直面する 任意のブロックを落下させて新しい状態を作る 処理、現在はO((HW)2)というあまりにも非効率な実装をしているがもう少し効率良くならないものだろうか。
AOJ 2311 お菓子の魔女
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2311
オセロを死ぬほど分かりにくく言うとこうなる。絶対競技プログラミングじゃないと思うけど、プログラミングではある。自分のコードめちゃくちゃ分かりにくいのですが「競プロerの書いたコードは読みやすい」とはいったいどういうことですかね・・・
