509.1

コーナーケースと想定解のお話。それから包除とやら。

250

見てない。

500

文字列を回文にしたいが、ある文字の挿入・削除・ある文字への書き換えのコストがそれぞれ与えられるので、最小のコストを求めよ、という問題。

削除を空文字への書き換え、挿入を空文字からの書き換え、と思って27文字で、全点間最小距離を求めておく。後は左端の文字または右端の文字を特定の文字に書き換えて挿入、あるいは両端の文字を特定の同じ文字に書き換える、という処理をしながら、DPでコストを求めるだけ。

1000

ある点から目的地への移動を考える。現在地に数字が書かれているとき、その数字分だけ、上・左・下・右のいずれかの方向に進める。数字が書かれていないとき、K回までに限り、任意の数字をそこに書き込んで良く、それに従って移動する。このとき目的地への最短距離のパスは何通りあるか答えよ、という問題。

現在位置に数字が書いてあればそれに従う。目的地から遠ざかる場合には、その分の距離をコストに加算。(このコストでダイクストラで良さそう。)数字を書くときは、数字の書いてある地点、または目的地に、KのうちのM回数字を書く処理を使って移動することを考える。途中の地点の場合は、包除のフラグを覚えておいて、後はごちゃごちゃ計算すれば良さそう。後でちゃんとやる...。