AtCoder Grand Contest 058 B問題メモ

AtCoder Grand Contest 058

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$ より大きいのが初めて出てきた位置を $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

Python3