KUPC 2019 D - Maximin Game

• 問題
• AC

とりあえずDPっぽいものから考えた。カード$1$から順にカード$N$まで二人に配っていくとして、千咲さんに$x$枚、月乃瀬さんに$y$枚配った時点で、条件に合っているような配り方の総数を$dp[x][y]$とする。遷移としては

$(S_x=1$かつ$x\le y)$または$(S_x = 0$かつ$x > y)$なら

$dp[x][y] += dp[x-1][y]$

$(S_y=0$かつ$y \le x)$または$(S_y = 1$かつ$y > x)$なら

$dp[x][y] += dp[x][y-1]$

で求まるが、${\mathcal O}(N^2)$なので制約的に無理だし、実はメモ化再帰で枝刈りされるみたいなこともないし、うまい高速化も思いつかないし……となって困っていた。

こういう問題の言い換えとして、原点$O$からスタートして千咲さんがカードを取ったらベクトル$(1, 1)$に沿って進み、月乃瀬さんが取ったらベクトル$(1, -1)$に沿って進むというのがあったなと思い出して実験してみると、次のような性質が見える:

• $O$からスタートして$(2N, 0)$に着く
• $y$座標が正の時は月乃瀬さんが勝っていて、$y$座標が負の時は千咲さんが勝っている。つまり、文字列$S$で勝ち負けが切り替わるところで$x$軸と交わる。

すなわち、$S$中で$0$が連続している部分では$x$軸の上にいなければならず（$x$軸を踏んでも良い）、$1$が連続している部分では下にいなければならない。このパスの数え上げは有名なのがあった気がすると思ってググったらカタラン数だった。同じ要素が連続している各部分列についてカタラン数を求めてかけ合わせれば答えになっている。