解いた & 解けなかった

解いた：
2244 : Dungeon Quest II
2249 : Road Construction
2250 : Operator
2251 : Merry Christmas

解けなかった：
1273 : The Best Name for Your Baby

2244 : 普通のDP．
2249 : 難しそうに見えるけど，ダイクストラしてやるのがよい．
2250 : 2分探索できそうでできないパターン(Ex.いつかのTopCoderの"Sheep"という問題)．なのでオペレーターの数を1から始めて1つずつ増やすしかないのだけど，計算量がさっぱり見積もれない．余裕でO(N^3)くらいかかりそうな気がするのだけど，なぜか普通に間に合ってしまう．イベント駆動の実装で無駄にかなりはまってしまった．実装力が欲しい…
2251 : DAGの最小パス被覆問題に帰結される．これは2部グラフのマッチングに帰結できる… らしい．トリッキーすぎる．最小費用流でもOKとか．2部グラフは良い性質持ちすぎで奥が深い．

1273 : 文脈自由文法の問題．DPっぽいなーと雰囲気だけはつかめるけど，サイクルとかある場合の処理が面倒くさすぎてやってられない．解説のスライドらしきものを発見したので読んでみると，Chomsky normal form に直すのがいいとか書いてあったので，それっぽいことをしてみる．しかしそれだとひどいパターンで文法のルールが大量に生成されてしまって大変なことになってしまったので諦めた．きっとあと1歩くらいのところにはいそうな気がするので後日また再チャレンジしたい．