AGC埋めが捗ります

概要

箱の中に赤い積み木と青い積み木が合計$N$個ある。

次の一連の操作を合計$M$回行う。

この操作を行った後、取り出した積み木を取り出した順番に重ねる。この$2M$個の色の組み合わせは何通り?

考察

要するに上のような操作なので、とりあえず$$DP[今何回取り出したか][今箱の中に赤が何個残っているか]$$を書きたくなるが、これがダメであることはテストケース1からわかる。なぜダメなのかを考えると、取り出した積み木の色と操作は必ずしも一対一対応しないからである。

テストケース1でいえば、赤0個青2個の状態から「青、青、赤、青、赤、赤」と取り出しても赤1個青1個の状態から「青、青、赤、青、赤、赤」と取り出しても同じ列が生成される。

ここでどのような操作で重複が起こるか考えると、

グリッドっぽいグラフ上で平行な操作で重複が起きている。このように重複が起きている場合どうにかして取り除くか、重複のカウントを止めなければいけない。そこで、部分列DPのように何らかの規則を定める。

(参考: drken氏の部分列DPについての記事。わかりやすい。)

どのような規則が適応できるか考える。図2においての右2本を数えないようにするためには、「平行な移動たちは最も左にあるものだけをカウントする」ようにしてやればいい。

(このような移動をcountableと名付ける)

そこで、countableな移動について考えてみる。そうすると、次のことが言える。 「countableな移動は、グラフの各行の最も左の点を少なくとも1つ通っている。」

(もしあるcountableな移動に関して各行の最左点を一つも通っていないとすると、移動のパス上の頂点を全て左に1つずつずらすことができ、countableの条件に反する。)

これは元の問題文では、「箱の中の赤い積み木が0になったタイミング」と同じ意味である。

あとはこれを満たすパス数を数え上げればいいので、

$$dp[i][j][k]=(i回取り出し、今赤い積み木がj残っていて、残り赤積み木が0になったことがある/ない)$$と定義することで、この問題が$O(NM)$で解ける。

メモリが厳しいので適宜再利用する。