AGC021-F Trinity - あああああ

金diff！

問題

概要

日本語なので省略

公式解説より見通しがいい感じの解法になった気がするので書きます

ネタバレ避け

解法

列の組(A,B,C)に対応する黒マスの塗り方は、AでもBでもCでも関わらないような黒マスを作らないようにすれば一意に決まります。

よって、次のようなマスの塗り方を数えれば良いです。

全ての黒マスについて、以下の条件1,2,3のいずれかが成立する。

1. 自分より左に黒マスがない。

2. 自分より上に黒マスがない。

3. 自分より下に黒マスがない。

右の列から黒マスの配置を決めていくことにします。

このとき、条件2,3のいずれにも関わっていない黒マス(つまり、一番上でも一番下でもないもの)は、条件1を満たしている必要があるため、それ以降(それより左の列)はその行には置けない、とすることになります。

dp[i][j] = 右 i 列を見て、 j 行はもう黒マスを置くことができない、とした通り数とします。

遷移を考えます。

右から i 列目に置く黒マスの個数で場合分けします。

0個の場合

dp[i+1][j] += dp[i][j]

1個の場合

これは、j 行以外ならどこにでも置けて、黒マスを置くことができない行の数は変わりません。

dp[i+1][j] += dp[i][j] * (H-j)

2個以上の場合

これも、j 行以外ならどこにでも置けて、新たに j - 2 行が黒マスを置くことができない行になります。なぜなら、一番上と一番下以外の j - 2 個は条件1を満たすようにするしかないからです。

dp[i+1][j+k-2] += dp[i][j] * (H-j) C k

これをそのまま実装すると、O(N^2M)で部分点が取れます。

あとは畳み込みで高速化するとO(NMlogN)になり、満点が取れます。

実装