サントリープログラミングコンテスト2024（AtCoder Beginner Contest 357）G問題メモ

サントリープログラミングコンテスト2024（AtCoder Beginner Contest 357）

G - Stair-like Grid

• $N$ 行の特殊な形をしたグリッドがあります。($N$ は偶数)
• 上から $i$ 行目にはマスが左端から $\left \lceil \frac{i}{2} \right \rceil \times 2$ マス並んでいます。
• 上から $i$ 行目、左から $j$ 列目のマスを $(i, j)$ と表します。

N = 6
□□
□□
□□□□
□□□□
□□□□□□
□□□□□□

• 各マスは空きマスと壁マスのいずれかです。壁マスは $M$ 個あり、$i$ 個目の壁マスは $(a_i, b_i)$ にあります。ただし $(1, 1)$ と $(N, N)$ は空きマスです。
• $(1, 1)$ を出発して、右または下に隣り合う空きマスへの移動を繰り返して $(N, N)$ へ辿り着く方法は何通りありますか？答えを $998244353$ で割った余りを求めてください。

• $2 \leq N \leq 2.5 \times 10^5$
• $N$ は偶数
• $0 \leq M \leq 50$
• $1 \leq a_i \leq N$
• $1 \leq b_i \leq \left \lceil \frac{a_i}{2} \right \rceil \times 2$
• $(a_i, b_i) \neq (1, 1)$ かつ $(a_i, b_i) \neq (N, N)$
• $i \neq j$ ならば $(a_i, b_i) \neq (a_j, b_j)$

公式Editorialにもあるが、通常の $H \times W$ のグリッド中に（2乗が通る程度の）$M$ 個の壁マスがある、という問題であれば、EDPC Y - Grid 2 で既出。

全体から壁マスを通過する経路を引く。壁マスも通過できるとして、（確実に）踏んだ壁マス数により包除原理DPをおこなう。

• $\mathrm{DP_{仮}}[i,k]=$ いま壁マス $i$ にいて、これまでに踏んだ壁マス数が $k$ 個以上の場合の経路数

さらに、「壁マス $i$ にいる状態から、次に壁マス $j$ に行く」という遷移は、これまでに踏んだ黒マス数 $k$ に依らず一定である。 （共通して、$i→j$ への経路数がかかる）
こういう場合、個数すら省略して、偶奇（正にかかるか負にかかるか）だけにまとめてしまえる。

• $\mathrm{DP}[i]=$ いま壁マス $i$ にいる場合の、（踏んだ黒マスが偶数の場合の経路数）-（奇数の場合の経路数）

• Educational DP Contest W,X,Y問題メモ
• [EDPC-Y問題 Grid 2] Educational DP Contest を Pythonで解く

               ＼
               ○＼      ○: 追加した空きマス（始点・終点）
□□           □□＼    ■: 追加した壁マス
□□      →   □□■＼
□□□□       □□□□＼
□□□□       □□□□■＼
□□□□□□   □□□□□□＼
□□□□□□   □□□□□□○＼

$N+2$ の階段状のグリッドにして、$i=j$ のナナメラインのマスは踏んではいけないとする。
また、2段に1段、一番右のマスは踏んではいけないとする。
この上で、左上の○→右下の○の経路数は、元の問題と同じである。

こういうグリッドの $(i_1,j_1)→(i_2,j_2)$ の経路数は、カタラン数や鏡像法を使って、階乗の事前計算のもとで $O(1)$ で求められる。

2点間の経路数が高速に計算できるなら、EDPC Y と同等の手法が使える。。。
のだが、全ての壁マスを同等に扱うと $O((N+M)^2)$ かかるのでTLE。

本来の壁マスと異なり、追加した壁マス（「角マス」とする）同士の遷移は規則的になることを利用して、分割統治FFTをする。

ある角マス $i$ に対して $0～i-1$ の角マスのDPが分かっている場合、 角マス間の遷移はカタラン数の偶数番目 $c_2,c_4,c_6,...$ を、$DP[i-1],DP[i-2],...$ と掛け合わせたものの合計となる。

○----- x132-,     DP[i-3] x 132
□□         |
□□■-- x14-|     DP[i-2] x  14
□□□□     |
□□□□■x2-|   + DP[i-1] x   2
□□□□□□ v   ---------------
□□□□□□■     DP[i]

こういう形のDPは、分割統治FFTで $O(N \log^2{N})$ で求められる。

• 解説 - AtCoder Beginner Contest 213

あとは、本来の壁マスの遷移を、分割統治の間に挟み込む。
角マスのDPを $\mathrm{DP}_1$、壁マスのDPを $\mathrm{DP}_2$ のように、分けて管理する。

「遷移元となるのは、値が確定してもう更新されないDP」（そうしないと、遷移元が更新されるたびに遷移先も更新が発生する）という点に注意すると、 角マスの $\mathrm{DP}_1[i]$ が確定するのは、分割統治FFTで $[i,i+1)$ の処理に来たときである。
そのタイミングで、壁マスに関する遷移を計算する。

確定した角マス i からは、そこから右下の壁マスに遷移できる

○
□□ i
□□■        ×: DP1[i] が確定した際、i からの遷移を計算する壁マスの範囲
□□××
□□××■
□□××××
□□××××■

i からの遷移を計算し終えたら、i の下にある壁マスも（壁マス同士を除いては）確定する

○
□□ i
□□■        ×: DP1[i] から壁マスへの遷移を計算した後、
□□××          DP2[j] が確定する範囲（壁マス同士を除いて）
□□××■
□□××□□    →×の中で左上の壁マスから順次確定させていける
□□××□□■

「×内の壁マス→それより右下の壁マス・角マスの遷移」を左上から計算し、DPに足し込んでおく。

その後、分割統治FFTの続きを再開すれば、正しいDPの値となる。

壁マスにまつわる遷移は、$M$ 個それぞれで、計 $O(N+M)$ 個の他の黒マス {から/へ} の遷移を計算するため、$O(M(N+M))$ かかる。

あわせて、$O(N \log^2{N} + M(N+M))$ となる。

PythonだとTLEがやや厳しいが、畳み込み部分だけでもNumbaで高速化したりすると通る。

Python3