AtCoder Regular Contest 097 E - Sorted and Sorted
ポエム
コンテスト中に通せませんでしたね…ほげほげ。
コンテスト中はひたすら貪欲を探していました、盲目状態、非常によろしくない。
解説を見て通したわけですが。
これは最適な並べ方について、明確に「こうじゃ！」みたいな貪欲が出せないんですよね。
そうすると焦って頑張って貪欲探そうとします。ああ、本当によろしくない。
これ見つかるわけないもんね、答えないんだものね。
こうゆうのは最初に全探索するべきだと考えるべきなんですね。(そっからＤＰに、まあこの過程はワンステップでいいんだろうね。)
だた、何について探索するべきなのかというのが(自明ではあるのだろうけれど)見つけづらいのが難点。
解説放送では慣れだと言ってましたね、慣れるしかなさそうだ。
まあ、ただ貪欲にはまるのだけは本当によろしくなくて(三回目)、貪欲にはまったらその方針が間違っていることを考えるべき。
さてさて、解法の話です。
ＤＰをやるということで、どの状態を考えるかですが、それは
dp[i][j] := 黒i個、白j個まで並べ終わったときの最適
で、この遷移について考えると、次に並べるのは黒のi+1か白のj+1になるのでそのどちらかになる。
これを貰うdpで書くと
dp[i][j] = min(dp[i-1][j] + moveB[i][j],dp[i][j-1] + moveW[i][j])
dp[i][j] は dp[i-1][j]からi個目の黒を動かしたときか、dp[i][j-1]から白のj個目を動かしたときのうち小さいほう
みたいな感じ。実際遷移は上げる方で書きましたが、書くときは大体もらう方が書きやすいですね。
moveB[i][j],moveW[i][j]をそれぞれ
moveB[i][j] = 黒をi-1個、白をj個並べた状態で、i個目の黒を移動させるのにかかるコスト
moveW[i][i]j = 黒をi個、白をj-1個並べた状態で、j個目の白を移動させるのにかかるコスト
となります。
これについては初期状態において(何も並べ替えていない状態？)今注目しているものの左にいくつまだ並べていないとされているものがあるかみたいなものと同じで(日本語むっず)、iまたはjを固定すると累積和っぽく求めることができますね。
ということで、流れとしては
moveW,moveBを計算してから(O(N^2))
dpテーブルを埋める(O(N^2))
となりますね。
600ですかー。これ。
600ですね。おそらく。
典型っぽいものね。うんうん。
