ABC062 D - 3N Numbers
問題
提出コード
やること自体は同じだったのですが、想定解がすごい綺麗で感動しました。ここでpriority_queueが使えるのですね～
解法
この問題は、初期値を(前からNの長さの部分の総和)-(後ろからNの長さの部分の総和)とし、
真ん中のNの長さの部分を、
前から要素を1つ取り、捨てる、もしくは前の長さＮの部分の好きな数字と置き換える
後ろから要素を1つ取り、捨てる、もしくは後ろの長さＮの部分の好きな数字と置き換える
という2つの操作から1つ選び実行することをN回繰り返して、(前からNの長さの部分の総和)-(後ろからNの長さの部分の総和)を最大化する問題になります。
数列を前からN個ずつ順番にa,b,cとすると、
(aの総和)-(cの総和)を最大化する問題となります。
数列bの先頭の数字を選んだら、その数字を捨てる、もしくはaの中の好きな数字と交換ができ、末尾の数字を選んだら、その数字を捨てる、もしくはcの中の好きな数字と交換ができます。
さて、bからとってきた数字は好きな数字と置き換えることができるので、
aは小さな数字から優先的に取り除く
cは大きな数字から優先的に取り除く
とするのが有効です。
この手の問題を解くときは前から操作する回数と後ろから操作する回数が合わせてN回なので、bの先頭とaに対する操作をk回、bの末尾とcに対する操作をN-k回行う、と固定した場合の解を求め、kについて全探索すればよいです。
さて、aに対する操作をk回行うと決めた時、どのようにするのが最適かを考えます。
k-1回操作した場合の最適解がすでに求まっているとします。
今現在のaからは、できるだけ小さな数字から優先的に取り除くのが正解です。
ということで、k回目の操作は、
aの最小値がbのk番目の値より小さければ、置き換える。この際、総和はその差分だけ増える
aの最小値がbのk番目の値以上であれば、k番目の数字を捨てる。この際、総和は据え置き
となります。
総和は増えていくだけなので、累積和のように記録していくことで、初期状態からどれだけ総和が増えたかを記録することができます。
cに対する操作は、今のことと真逆の操作をします。cに対するk回目の操作では、cの最大値がbの後ろからk番目の値より大きければ、数字を置き換えます。差分だけ、初期状態から総和が増加します。
これらは、RMQを利用し、現在の最小(大)値を取り出して、うまく更新していくことで、調べることができます。想定解は優先度付きキューを利用していました。こちらのほうが実装はもちろん楽ですね。
あとは、aに対してk回操作を行い、cに対してn-k回操作を行った場合の解が求められるようになったので、kについて全探索を行うことで、この問題が解けます。
