607.1

結果を見れば適切な点数配分のような気はするけれど、模範解答を聞いたらそんなバカな、となるような問題...。

250

小文字のアルファベットからなる文字列が与えられる。一部は文字が読めないので、どれか分からない。すべての可能性が等確率で起こるとしたとき、その文字列の中に含まれる回文文字列の個数の期待値を答えよ、という問題。

取り敢えず回文の中央の位置決めて、2文字ずつ長くしていく感じでやる。中央は文字列長の二倍程度の個数しかない。一致しないなら打ち切ってしまえばいいし、分からない文字あるなら、一致する確率を累計していけばいい感じ。

475

0から9までのダイヤルがN個並んでいて、隣接するK個を+1するか-1する操作を何回すれば、目的の状態にできるか答えよ、という問題。

自分の隣のヤツが回った方向と回数を覚えておくと、それ以内であればコストなしで便乗できる。ついでに便乗するだけじゃなくて、ちょっと余分に自分も回るとか、明らかに無視して逆方向に進む、とか、そういうのを全部覚えておくといいっぽい。とにかく全部の状態遷移をDPすれば通る。

1000

見てない。