551.1

入力のコーナーケースは全部試すくらいの注意が必要。さすがに全部はムリなので、どれが考慮すべきなのか適切に見極めることが...。

250

文字列が与えられるので、隣接する文字のスワップを指定された回数だけして良いので、特定の文字ができるだけ連続するようにせよ、という問題。

基本的には一箇所に集める作業をする。集まる場所を決めれば、左右から近いものを優先的に移動させていくだけ。

本当は集める文字の左端と右端を決めると、中央の文字に集めるのが最適になるのを暗黙に使っている。ある位置に集めるのをやめて、隣の文字に集める場合、(集め終わった結果から逆算して)隣の文字より向こうのヤツは1個ずつ戻って、自分より反対側のヤツは1個ずつ進むので、集める位置の差分に左右の個数の差分を乗じた数だけコストが変動する。なので中央に集めるのが最適なはず。

で、最初に書いた、集める場所を決める、というのを全部試せば、任意のパターンについて、最適な集まり場所は網羅されていて、集まれるだけ集まるという処理をしているので、できるだけ範囲の広いのが取得できているはず。(中央じゃない点にたくさん集まる場合もあるけれど、最適値よりも良くなることはない。)

450

隣接行列が与えられる。移動の際に、一番IDの小さい点に移動しないといけないという制約がある。行列を書き換えて良いので、始点から終点に移動する場合に必要な書き換えの最小数を答えよ、という問題。

結局二点間の移動コストを書き換えの回数にしてグラフを作り直してダイクストラするだけ。ダイクストラなので、グラフの作りかえと探索を同時にやっても良い。

1000

グラフ。ちょっと最初からやり直す必要ありそう。