C,D,Eでどれに注力するかを見誤った感じはするが、じゃあどうやって見分けられてたかというとわかんないんだよな。
区間DPかな、と思うが、どうしても O(N^2M) くらいの計算が必要になってしまう。
あと重複を除くのも結構手間がかかる。
あり得る全ての数列に対して和を求める問題であることを活かして、もっとガサッとまとめて計算できる方法があるはず。
A を固定して、どういう場合に複数要素をまとめて更新できるか考えると、
... 3 3 3 3 ....... ○同じ要素が複数連続している
... 3 7 3 5 6 3 ... ○同じ要素が、自身より大きい要素のみを挟んで複数ある
~ ~ ~
... 3 7 1 5 6 3 ... ×ただし小さい要素を1つでも挟んでいるとダメ
~ x ~ 1を1のまま残すためには、3は2回に分けて操作しないといけない
まとめて更新できる箇所を (i,j,k,...) とする。
まとめて更新できるとは、言い換えると
「本来、所定の値にするのに1要素につき1回の操作が必要になるところ、i に操作をしたら j,k,... は操作を省ける」と言える。
どれだけ操作を省けるかを全体から引くことで答えを求める。
一旦、全てのあり得る整数列について、操作回数の最大値である N 回必要と仮定してしまう。N \times M^N。
そこから、「自身に対する操作を省ける要素 × そのような要素が出現する数列の個数」を引く。
「自身に対する操作を省ける要素」はつまり、上図のように「自身より左に、自身より小さい要素を挟まず同じ数字が存在している」要素となる。
この個数を数えるため、以下のDPを定義する。
この時、各 DP[i][j] につき、DP[i][j] \times M^{N-i-1} だけ、j の操作を省ける数列が存在する。
,---------- i個 -----------, ,---- N-i-1個 ---, [ DP[i][j]が示すような数列 ] j [ 何でもよい ]
各 j=1～M につき DP[0][j]=0 で初期化する。
DP[i][j] を求める。末尾要素で場合分けして考える。
あわせて DP[i][j]=M^{i-1}+(M-j) DP[i-1][j] となり、O(NM) で更新していける。
いわゆる「縦に見るものを横に見る」「主客転倒」のテクニックを、(i,j) を“主”として行うイメージ。
これにより他の状態がどうなっていても重複を気にせず、1箇所の操作を省けるか省けないかに注視できる。
目標状態が達成されたとき、コマがどこにあるべきかが重要となる。
目標状態で赤と青（青と赤）の境目、つまり各 l_i,r_i を「変曲点」とする。
ある座標について、「そこに初期状態で置かれたコマが、奇数個、他の座標に移動する」か、「他の座標から、そこに奇数個のコマが移動してくる」とき、その座標が変曲点となる。 ただし、両方同時に起こった場合は相殺されて変曲点とならない。
1 5
o コマを1個、5に動かすと、
初期 o 1にとっては「初期状態で置かれたコマが奇数個他に移動」
目標 |-----| 5にとっては「他の座標から奇数個のコマが移動してくる」となり、目標状態となる
1 3 5
o コマを3からそれぞれ1,5に動かすと目標状態となる
初期 o 3はコマが偶数個移動するので変曲点にならない
目標 |-----|
1 3 5 1→3, 3→5 へ移動させると目標状態となる
初期 o o 3は、両方の条件が同時に起こってるので変曲点とならない
目標 |-----|
但しこの場合は1→5へ一気に移動させても同じなので、
あくまで「その移動方法と同一視できる」というだけ
すると、目標状態の時に、各座標に置かれていなければならないコマの偶奇は一意に決まる。
最終的にコマが置かれる座標の候補は、「初期状態でコマが置かれていた座標」と「変曲点の座標」だけを考えればよい。
それ以外の座標にコマを置くのなら、変曲点であってはいけないのでどこかから偶数個のコマを移動させてきたことになるが、それなら最終地点をどちらかの初期座標に寄せても色の状態・移動回数は損しない。
ある候補座標について、
と、最終的にコマが置かれるべき個数の偶奇となる。i 番目の候補座標についての偶奇を x_i とする。
x_i=0 となった座標は0個でも2個でもよいが、x_i=1 の場合は最低1個は必要なので、そのような座標がコマの数 N より大きければそもそも不可能となる。
逆に足りていれば、移動距離はともかく x_i=1 の座標にコマを1個ずつ持っていけて、また余ったコマがあったとしても必ず偶数個となるので、達成可能となる。
コマの初期位置と最終位置の割り当てを、偶奇が合うように決めながら、総移動距離を最小化させたい。
候補座標をソートし、DPをする。
ある区間に、割り当てが決まっていない初期位置のコマと、割り当てが決まっていない最終位置のコマが両方存在することは無駄。
仮にそうなるとしたら、i 番目より前の候補座標のどこかで
「未割り当ての初期位置のコマが残っているのに、未割り当ての最終位置を増やした」ようなことが生じているはずなので、そこでマッチングさせた方が必ずよい。
よって、DPではどちらがどれだけ余っているかだけ管理しておけばよい。
i 番目の候補座標を t_i として、次の候補座標 t_{i+1} までの距離を d_i とする。
この間に |j| 個の未割り当てがある状態では、総移動距離は |j| \times d_i だけ増える。
これをもとにDPを更新する。
実際には達成不可能な j が多いので、辞書型などでもって更新していくとよい。
最初、DP[0][0]=0 である。最終的に DP[候補座標数][0] が答えとなる。
変曲点である。必ずどこかからコマを1つ持ってくる必要がある。3つ以上持ってくる必要は無い。
DP[i-1] で可能な各 j につき、DP[i][j+1] = DP[i-1][j] + d_i|j+1| となる。
c 個のコマがあったとする。
x_i=1 の場合、初期位置から1個動かさないことにして総移動距離は損しない。自由に使えるコマは1個減る。
c-1 を新たな c とすると、x_i=0 の時と同じように考えられる。
その場に残すコマ数を偶数個にしたいので、他の座標に移動させなければならないコマ数の偶奇は c と一致する。
c が偶数の時、移動させるコマは、以下のことに使える。
要は、j を 0,2,...,c だけ減少させる操作となる。この減少幅を s とすると、
c が奇数の時、以下のことが出来る。
3つめが見落としがちだが、サンプル4のようなケースに対応するためには必要となる。
実際の操作で説明すると、コマを敢えて1個残し、自分より右側のコマに来てもらって相殺させて整合を図る方法となる。
要は、j を奇数単位で -1～c だけ減少させる操作となる。更新操作は偶数の時と一緒。
これで最適な割り当てが求められる。
実際には、例えば未割り当ての最終位置がある場合に、初期位置のコマが余っていてマッチングさせない理由は無いのでもう少し枝刈り出来そうだが、ややこしいのでパス。
実装すると3重ループとなるが、
なので、O((N+K)^2) 程度で回る。実際は j の取り得る範囲など、もっと小さいはず。
たまに見る解法なのに、問題設定に上手く溶け込まされているとパッとたどり着けないもんだね。
黒マスを分かつ罫線と分かたない罫線は、操作を重ねても変わらない。
分かたない罫線それぞれについて「その罫線で操作が行われる確率」を求めると、
それを全て足し合わせたもの+1（最後に黒マスを分かつ操作）が答えとなる。
操作列を固定して各々の長さを考えるのでは無く、罫線を固定して各々が操作される確率を求める。
いわゆる主客転倒。
で、肝心の確率だが、ある罫線が操作されない場合というのは、
1 2 3 4 5 罫線1で操作されるためには、 6_ □ □ □ □ □ □ 黒マスを分かつ罫線(4,7)や 7_ □ □ □ ■ □ □ 自身と同じ側で自身より黒マスに近い罫線(2,3)で □ □ □ □ ■ □ 先に操作されてはいけない
で、「自身＋自身より先に操作されてはいけない罫線」の本数を K 本とすると、 この K 本だけに着目したときに「自身が一番先に操作される確率」は、\dfrac{1}{K} となる。
全ての分かたない罫線に付いて求めると O(H+W)。
また、黒マスを分かつ罫線を S 本、 上下左右いずれか1方向について、その方向に分かたない罫線が t 本あると、 その方向における期待値は \dfrac{1}{S+1}+\dfrac{1}{S+2}+...\dfrac{1}{S+t} となるので、 これを利用するともう少しすっきりと書ける。