競プロキャンプ2026関西 F - Keep Far
個の座席が一列に並んでいて、 人が順に 1 人ずつ座ります。各人は、左右の両隣に誰も座っていない空席があればその中から 1 つを選び、なければ空席から好きに 1 つを選んで座ります。最終的に座っている席が文字列 の # の位置と一致するような座り方の個数を、 で割った余りで求める問題です(、# はちょうど 個)。
両隣に誰も座っていない空席を「よい席」と呼びます。座り方は 2 つの段階に分かれます。
- 前半:よい席がある間は、よい席に座ります。前半に座る席の集合を とすると、 のどの 2 席も隣り合いません。
- 後半:よい席がなくなったら、残りの人は好きな空席に座ります。人が増えるとよい席は減る一方なので、後半によい席が復活することはありません。
前半が終わるのは、 に入っていないどの席にも、隣に の席があるときです。
隣り合う # がないとき
Section titled “隣り合う # がないとき”人とも、座る時点で両隣が空いています。よって、どの順に座ってもルールに従っていて、答えは です。
隣り合う # があるとき
Section titled “隣り合う # があるとき”隣り合う 2 席のうち後に座る人は、よい席でない席に座るので、後半に座っています。よって、前半は最後まで終わっていなければなりません。つまり は次の条件を満たします。
- は
#の席だけからなり、どの 2 席も隣り合わない。 - に入っていない席(
.の席も含む)はすべて、隣に の席がある。
特に、どの # とも隣り合わない . があれば、この条件を満たす はないので答えは です。
逆に、条件を満たす を 1 つ決めて とすると、前半の 人は の席に好きな順で座れて 通り、後半の 人は残りの # の席に好きな順で座れて 通りです。したがって、条件を満たす のうち のものの個数を として、答えは
です。
を DP で数える
Section titled “cic_ici を DP で数える”の席を左から とすると、条件は次のように言い換えられます。
- どの も
#の席である。 - は か である(隣り合わず、間の席はどれも の席と隣り合う)。
- は か 、 は か である(両端の席も の席と隣り合う)。
そこで、席を左から見ていき、「直前に選んだ席が何個前か」と「これまでに選んだ個数」を状態にして DP をします。計算量は です。
C++
#include "shogo-library/base/all"#include "shogo-library/math/combinatorics.hpp"#include "shogo-library/math/modint.hpp"#include "shogo-library/utility/container_func.hpp"
using mint = modint998244353;using C = Combination<mint>;
void solve() { LL(N, K); STR(S); ll full = true; rep(i, N) { if (S[i] == '#') continue; if (i > 0 && S[i - 1] == '#') continue; if (i < N - 1 && S[i + 1] == '#') continue; full = false; } rep(i, 1, N) { if (S[i - 1] == '#' && S[i] == '#' && !full) { print(0); return; } } if (not full) { print(C::factorial(K)); return; } ary<vec<mint>, 3> dp = {vec<mint>(N + 1), vec<mint>(N + 1), vec<mint>(N + 1)}; dp[1][0] = 1; for (char c : S) { vec<mint> ndp(N + 1); if (c == '#') { rep(i, 1, N + 1) { ndp[i] += dp[0][i - 1]; ndp[i] += dp[1][i - 1]; } } std::swap(dp[0], dp[1]); std::swap(dp[1], dp[2]); std::swap(dp[2], ndp); } mint ans = 0; rep(i, K + 1) { ans += C::factorial(K - i) * C::factorial(i) * (dp[1][i] + dp[2][i]); } print(ans);}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}full は「どの . の席も # の席と隣り合う」かどうかです。full でないときは、隣り合う # があれば 、なければ を出力します。full のときは、隣り合う # がなくても DP に進みますが、そのときは がすべての # の席になるしかないので、DP でも が求まります。
DP では、今の席を見る直前の時点で、dp[2][i] が「直前の席を選んだ」、dp[1][i] が「2 つ前の席を選んだ」、dp[0][i] が「3 つ前の席を選んだ」状態で、 個選んだときの場合の数です。今の席が # なら、dp[0] と dp[1] から今の席を選べます。そのあと 3 つの配列をずらして、次の席から見た状態にしています。はじめに dp[1][0] = 1 としているのは、席 の 2 つ左に仮の席が選ばれているとみなすためで、こうすると最初に選ぶ席は か になります。最後は、最後に選んだ席が か である dp[2] と dp[1] を使います。
modint998244353 は で割った余りで計算する整数型で、C::factorial(n) は を返します。場合の数は非常に大きくなるので、DP の配列も mint にしておく必要があります。
使用ライブラリ:cpp_include@9c33ee7