AtCoder Regular Contest 114 C,D,E問題メモ

AtCoder Regular Contest 114

C,D,Eでどれに注力するかを見誤った感じはするが、じゃあどうやって見分けられてたかというとわかんないんだよな。

C - Sequence Scores

• 整数 $N,M$ が与えられる
• 長さ $N$ の整数列 $A$ に対し、$f(A)$ を以下で定義する
  • 長さ $N$ で、$0$ で初期化された整数列 $B$ を用意する
  • 以下の操作を繰り返して、$B$ を $A$ に等しくするための最小操作回数を $f(A)$ とする
  • 操作
    • 3つの整数 $(l,r,x)$ を決める
    • $i=l,l+1,...,r-1,r$ に対して $B_i$ を $\max(B_i, x)$ で置きかえる
• 長さ $N$ で各要素が $1$ 以上 $M$ 以下の整数列は $M^N$ 個ある
• $f(A)$ を全てに対して求め、その総和を $\mod{998244353}$ で出力せよ
• $1 \le N,M \le 5000$

区間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]=$ 長さ $i$ で、末尾に $j$ を付け足したとき、その $j$ の操作を省けるような数列の個数

この時、各 $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]$ を求める。末尾要素で場合分けして考える。

• 末尾が $j$
  • 末尾以前の要素がどうあろうと、操作は省ける。$M^{i-1}$ 通り
• 末尾が $j+1$ 以上
  • 末尾要素は $M-j$ 通り、それ以前の要素は $DP[i-1][j]$ 通り
• 末尾が $j-1$ 以下
  • 不可能。0通り

あわせて $DP[i][j]=M^{i-1}+(M-j) DP[i-1][j]$ となり、$O(NM)$ で更新していける。

いわゆる「縦に見るものを横に見る」「主客転倒」のテクニックを、$(i,j)$ を“主”として行うイメージ。
これにより他の状態がどうなっていても重複を気にせず、1箇所の操作を省けるか省けないかに注視できる。

Python3

D - Moving Pieces on Line

• 無限に続く数直線があり、はじめ、全ての区間は青い
• $N$ 個のコマが整数座標上に置かれている
  • コマ $i$ は座標 $a_i$ に置かれている
  • 同じ座標に複数のコマが置かれている場合もある
• 以下の操作を好きなだけ繰り返す
  • コマを1つ選び $\pm 1$ のいずれかの整数座標に動かす
  • その時、コマが移動した区間の色が青なら赤、赤なら青に反転する
• 最終的に、以下の目標状態に出来るか判定し、可能ならコマの移動距離の総和の最小値を求めよ
• 目標状態
  • $K$ 個の区間 $[l_i,r_i]$ のみが赤で、他が青
  • 区間は重複しないし隙間を空けず隣り合ってもいない
• $1 \le N \le 5000$
• $1 \le K \le 2500$
• $|a_i|,|l_i|,|r_i| \le 10^9$

目標状態が達成されたとき、コマがどこにあるべきかが重要となる。

目標状態で赤と青（青と赤）の境目、つまり各 $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へ一気に移動させても同じなので、
                   あくまで「その移動方法と同一視できる」というだけ

すると、目標状態の時に、各座標に置かれていなければならないコマの偶奇は一意に決まる。

最終的にコマが置かれる座標の候補は、「初期状態でコマが置かれていた座標」と「変曲点の座標」だけを考えればよい。
それ以外の座標にコマを置くのなら、変曲点であってはいけないのでどこかから偶数個のコマを移動させてきたことになるが、それなら最終地点をどちらかの初期座標に寄せても色の状態・移動回数は損しない。

ある候補座標について、

• 変曲点であれば $1$、そうでなければ $0$
• そこに、初期状態で奇数個のコマが置かれていた場合、$1$ をxorする

と、最終的にコマが置かれるべき個数の偶奇となる。$i$ 番目の候補座標についての偶奇を $x_i$ とする。

$x_i=0$ となった座標は0個でも2個でもよいが、$x_i=1$ の場合は最低1個は必要なので、そのような座標がコマの数 $N$ より大きければそもそも不可能となる。

逆に足りていれば、移動距離はともかく $x_i=1$ の座標にコマを1個ずつ持っていけて、また余ったコマがあったとしても必ず偶数個となるので、達成可能となる。

コマの初期位置と最終位置の割り当てを、偶奇が合うように決めながら、総移動距離を最小化させたい。

候補座標をソートし、DPをする。

• $DP[i][j]=i$ 番目の候補座標までの割り当てを決めたとき、割り当てが決まってない「最終位置数 - 初期位置数」が $j$ の場合の最小総移動距離

ある区間に、割り当てが決まっていない初期位置のコマと、割り当てが決まっていない最終位置のコマが両方存在することは無駄。
仮にそうなるとしたら、$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$ とすると、

• $DP[i][j-s] \xleftarrow[\min]{} DP[i-1][j] + d_i|j-s|$ となる。

$c$ が奇数の時、以下のことが出来る。

• 未割り当ての最終位置とマッチングさせる
• 未割り当ての初期位置を増やす
• 新たに未割り当ての最終位置を1個増やす

3つめが見落としがちだが、サンプル4のようなケースに対応するためには必要となる。
実際の操作で説明すると、コマを敢えて1個残し、自分より右側のコマに来てもらって相殺させて整合を図る方法となる。

要は、$j$ を奇数単位で $-1～c$ だけ減少させる操作となる。更新操作は偶数の時と一緒。

これで最適な割り当てが求められる。
実際には、例えば未割り当ての最終位置がある場合に、初期位置のコマが余っていてマッチングさせない理由は無いのでもう少し枝刈り出来そうだが、ややこしいのでパス。

実装すると3重ループとなるが、

• 1重目: 候補座標数 $O(N+K)$
• 2重目: DPで $j$ の取り得る範囲だが、$x_i=1$ の座標数を $M$ として $-M～M$ だけを持てばよいので $O(N+K)$
• 3重目: ある座標におけるコマの初期個数を $C$ として $O(C)$ だが、これはループ全体を通した合計が $O(N)$

なので、$O((N+K)^2)$ 程度で回る。実際は $j$ の取り得る範囲など、もっと小さいはず。

Python3

E - Paper Cutting 2

• $H \times W$ のグリッドとみなせる紙がある
• グリッドはちょうど $2$ マス $(h_1,w_1),(h_2,w_2)$ が黒で、他は白
• 以下の操作を繰り返す
  • 端を除く縦横の罫線の中から一様ランダムに1本選んで一直線にカットする
  • 黒マスが同じ側に残っていたら、残っていない方を捨て、残っている方の紙で操作を続ける
  • 黒マスが異なる側に分かれたら、操作を終了する
• 操作回数の期待値を $\mod{998244353}$ で求めよ
• $1 \le H,W \le 2 \times 10^5$

たまに見る解法なのに、問題設定に上手く溶け込まされているとパッとたどり着けないもんだね。

黒マスを分かつ罫線と分かたない罫線は、操作を重ねても変わらない。
分かたない罫線それぞれについて「その罫線で操作が行われる確率」を求めると、 それを全て足し合わせたもの+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}$ となるので、 これを利用するともう少しすっきりと書ける。

Python3