AtCoder Grand Contest 058 B問題メモ
B - Adjacent Chmax
問題
- $1～N$ の順列 $P=(P_1,...,P_N)$
- 「隣り合う2要素 $P_i,P_{i+1}$ を、$\max(P_i,P_{i+1})$ に置き換える」という操作を何度でも行える
- 操作後の $P$ としてあり得る数列の個数を $998244353$ で割ったあまりで求めよ
- $2 \le N \le 5000$
解法
変なDP。
性質を考えると「各数字は、自身より小さい値が続く限りは好きなだけ左右に浸食できるよ」と言い換えられる。
1 7 2 3 6 4 8 5
↓
1 7 6 6 6 6 8 5
この時、後からより大きい値に上書きされると、当初の位置から離れた位置にもその数字が来うるのが、少し見落としやすい。
1 7 6 6 6 6 8 5
↓
1 7 [6] 8 8 8 8 5 当初の位置と全く違う位置に来た6
区間DPや、最大値または最小値からパターン数を求めていくのも考えたが、あんまり上手くいかない。
結局、左から詰めていくのがよさげ。
- $DP[i][j]=$ 左から $i$ 項だけで考えたとき、$i$ 項目が $j$ であるような数列の個数
この時、右側の数字が遡って左側に浸食しうるというのが難点だが、そこは $i$ を遡って更新する。
いろんな遷移パターンを、注意深く見つけていく必要がある。
左端に“0”があったと見なした方が処理しやすいので、そうする。
i 0 1 2 3 4 5 6 7 8 9 10 j \ P (0) 4 9 6 3 8 10 1 2 7 5 --------------------------------------- (0) 1 1 2 3 4 5 6 7 8 9 10 ---------------------------------------- 計 1
$i$ 列を更新するとき、（$i+1$ 以降は後から更新するので保留として）
- $P_i$ を使う。$P_i$ は左側にも遡って浸食しうる
- $i-1$ 以前から浸食してきた数字を $i$ にも浸食させる
の2つとなる。
$P_i$ を使う
左にどこまで浸食できるかをまず求める。遡って見ていって、$P_i$ より大きいのが初めて出てきた位置を $k$ とする。
存在しない場合は $k=0$ とする。
（以下の表はまだ説明してない更新があるが、ひとまず所与として、今は $i=5$ について更新する）
k i
i 0 1 2 3 4 5 6 7 8 9 10
j \ P (0) 4 9 6 3 8 10 1 2 7 5
---------------------------------------
(0) 1
1
2
3 4
4 1
5
6 2 4
7
8 ? ? ? ? の位置を更新する
9 1 2 2 2
10
----------------------------------------
計 1 2 2 4 10
$l=k+1～i$ について、$DP[l][8]$ を求めていく。
求めたい箇所の手前（$l-1$）は何で終わっていようと問題ないので、$DP[l][8]$ にはその時点の $DP[l-1]$ の「計」がそのまま入ることになる。
$l=k+2$ 以降では、より左まで自身が浸食したパターンも含まれるので、自身による直前の更新も含めて加算する。
k i
i 0 1 2 3 4 5 6 7 8 9 10
j \ P (0) 4 9 6 3 8 10 1 2 7 5
---------------------------------------
(0) 1
1
2
3 4
4 1
5
6 2 4
7
8 [2]
9 1 2 2 2
10
----------------------------------------
計 1 2 [2] 6 10
i 0 1 2 3 4 5 6 7 8 9 10
j \ P (0) 4 9 6 3 8 10 1 2 7 5
---------------------------------------
(0) 1
1
2
3 4
4 1
5
6 2 4
7
8 2 [6]
9 1 2 2 2
10
----------------------------------------
計 1 2 2 [6]16
i 0 1 2 3 4 5 6 7 8 9 10
j \ P (0) 4 9 6 3 8 10 1 2 7 5
---------------------------------------
(0) 1
1
2
3 4
4 1
5
6 2 4
7
8 2 6[16]
9 1 2 2 2
10
----------------------------------------
計 1 2 2 6[16]16
浸食してきた値を使う
$i=5$ の更新を見る。今は浸食する更新のみを考える。
i
i 0 1 2 3 4 5 6
j \ P (0) 6 5 4 2 3 1
---------------------------
(0) 1
1
2 5
3
4 2 5 ? ? の位置を更新する
5 1 2 3 ?
6 1 1 1 1 ?
----------------------------
計 1 1 2 5 14
$DP[i-1]$ に値のあるうち、$4,5,6$ の3つの数字が浸食しうる。$2$ は $3$ より小さいため浸食し得ない。
性質を考えると、これは初期の $P$ の中では降順（6→5→4 の順）に出現しているはずである。
この内、最大である $j=6$ は、自身が $i$ まで来ようと思うとその間の全てを $6$ で覆い尽くすしかないので、 $DP[i-1][6]$ がそのまま $DP[i][6]$ に継承される。
一方 $j=5$ は、冒頭で「見落としがち」といったような、「$5$ を先に $i=5$ まで浸食させといて、後で $6$ を $i=4$ まで浸食させる」というものもあり得る。
6 5 4 2 3 ... ↓ 6 5 5 5 5 ... ↓ 6 6 6 6 5 ...
これも「$i$ 番目の項が $5$ である数列」として数えなければならない。
よって、$DP[i][5]$ には自身の継承分 $DP[i-1][5]$ に加え、$DP[i-1][6]$ からも遷移する。
一方で、$DP[i-1][4]$ からは遷移しない。もしそうなると、$P$ の初期値と $4,5$ の位置関係が逆転していることになり、そういうことは起こらない。
「自身より大きい、1つ前の値」から遷移できることになる。
従って $j=4$ は同様に考えると、$DP[i][4]=DP[i-1][4]+DP[i-1][5]+DP[i-1][6]$ となる。
これは、$j=N～(P_i+1)$ について $DP[i-1][j]$ に値が入っているところのみで、後ろから累積和を取ることで計算できる。
i
i 0 1 2 3 4 5 6
j \ P (0) 6 5 4 2 3 1
---------------------------
(0) 1
1
2 5
3
4 2 5 9
5 1 2 3 4
6 1 1 1 1 1
----------------------------
計 1 1 2 5 14 14
DPの更新は、この「$P_i$ を使う」「浸食してきた値を使う」の2パターンを両方行えばよい。
「$P_i$ を使う」では横方向、「浸食してきた値を使う」では縦方向に それぞれ最大 $N$ 回の更新・累積和の計算などを行うのみなので、 「計」もちゃんと管理しておくことで、計算量は $O(N^2)$ となる。
全て埋め終えたサンプル3は以下のようになる。
i 0 1 2 3 4 5 6 7 8 9 10 j \ P (0) 4 9 6 3 8 10 1 2 7 5 ------------------------------------------- (0) 1 1 45 2 45 135 3 4 4 1 5 405 6 2 4 7 45 180 360 405 8 2 6 16 9 1 2 2 2 2 10 1 3 5 11 27 45 45 45 45 45 -------------------------------------------- 計 1 3 5 11 27 45 45 180 360 405 855
