コンテンツにスキップ

競プロキャンプ2026関西 F - Keep Far

サイト
MOFE
コンテスト
競プロキャンプ2026関西
問題
F - Keep Far

NN 個の座席が一列に並んでいて、KK 人が順に 1 人ずつ座ります。各人は、左右の両隣に誰も座っていない空席があればその中から 1 つを選び、なければ空席から好きに 1 つを選んで座ります。最終的に座っている席が文字列 SS の # の位置と一致するような座り方の個数を、998244353998244353 で割った余りで求める問題です(1≤K≤N≤30001 \le K \le N \le 3000、# はちょうど KK 個)。

両隣に誰も座っていない空席を「よい席」と呼びます。座り方は 2 つの段階に分かれます。

  • 前半:よい席がある間は、よい席に座ります。前半に座る席の集合を II とすると、II のどの 2 席も隣り合いません。
  • 後半:よい席がなくなったら、残りの人は好きな空席に座ります。人が増えるとよい席は減る一方なので、後半によい席が復活することはありません。

前半が終わるのは、II に入っていないどの席にも、隣に II の席があるときです。

KK 人とも、座る時点で両隣が空いています。よって、どの順に座ってもルールに従っていて、答えは K!K! です。

隣り合う 2 席のうち後に座る人は、よい席でない席に座るので、後半に座っています。よって、前半は最後まで終わっていなければなりません。つまり II は次の条件を満たします。

  • II は # の席だけからなり、どの 2 席も隣り合わない。
  • II に入っていない席(. の席も含む)はすべて、隣に II の席がある。

特に、どの # とも隣り合わない . があれば、この条件を満たす II はないので答えは 00 です。

逆に、条件を満たす II を 1 つ決めて ∣I∣=i|I| = i とすると、前半の ii 人は II の席に好きな順で座れて i!i! 通り、後半の K−iK - i 人は残りの # の席に好きな順で座れて (K−i)!(K - i)! 通りです。したがって、条件を満たす II のうち ∣I∣=i|I| = i のものの個数を cic_i として、答えは

∑ii! (K−i)! ci\sum_{i} i! \, (K - i)! \, c_i

です。

II の席を左から p1<p2<⋯<pip_1 < p_2 < \dots < p_i とすると、条件は次のように言い換えられます。

  • どの pjp_j も # の席である。
  • pj+1−pjp_{j+1} - p_j は 22 か 33 である(隣り合わず、間の席はどれも II の席と隣り合う)。
  • p1p_1 は 11 か 22、pip_i は N−1N - 1 か NN である(両端の席も II の席と隣り合う)。

そこで、席を左から見ていき、「直前に選んだ席が何個前か」と「これまでに選んだ個数」を状態にして DP をします。計算量は O(N2)O(N^2) です。

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 でないときは、隣り合う # があれば 00、なければ K!K! を出力します。full のときは、隣り合う # がなくても DP に進みますが、そのときは II がすべての # の席になるしかないので、DP でも K!K! が求まります。

DP では、今の席を見る直前の時点で、dp[2][i] が「直前の席を選んだ」、dp[1][i] が「2 つ前の席を選んだ」、dp[0][i] が「3 つ前の席を選んだ」状態で、ii 個選んだときの場合の数です。今の席が # なら、dp[0] と dp[1] から今の席を選べます。そのあと 3 つの配列をずらして、次の席から見た状態にしています。はじめに dp[1][0] = 1 としているのは、席 11 の 2 つ左に仮の席が選ばれているとみなすためで、こうすると最初に選ぶ席は 11 か 22 になります。最後は、最後に選んだ席が NN か N−1N - 1 である dp[2] と dp[1] を使います。

modint998244353 は 998244353998244353 で割った余りで計算する整数型で、C::factorial(n) は n!n! を返します。場合の数は非常に大きくなるので、DP の配列も mint にしておく必要があります。

使用ライブラリ:cpp_include@9c33ee7