communication-hard

解説

問題の整理

$N$ 回の選択パートがあり、各パートでは $K_i$ 個の選択肢のいずれかを選びます。
選んだ選択肢に応じてコミュニケーションポイントが $-3$ から $3$ の範囲で増減します。

最終的なポイントが $X$ 以上となるような選び方の総数を求め、その結果を $4736947$ で割った余りを出力する問題です。

制約からの考察

• $N \leq 1000$
• 各選択の増減は $[-3, 3]$ の範囲
  → 最終的なポイントは $[-3N, 3N]$ の範囲に収まります。

したがって、DP で「到達可能なスコアの分布」を管理できます。

解法方針

1. 状態の定義

DP を次のように定義します：

$$dp[i][s] = i \text{ 回の選択を終えたとき、スコアが } s \text{ である通り数（mod } 4736947\text{）}$$

ただし $s$ の範囲は $[-3N, 3N]$ です。

2. 遷移

$i$ 回目の選択で値 $k \in [-3, 3]$ を選んだとき、
そのスコア $k$ が出現する回数を $cnt_i[k]$ として数えておきます。

すると遷移は

$$dp[i+1][s+k] \;+=\; dp[i][s] \times cnt_i[k]$$

です。
範囲外に出る遷移は無視します。

3. 初期条件

• $dp[0][0] = 1$
• それ以外は $0$

4. 答え

最終的な答えは

$$\sum_{s = X}^{3N} dp[N][s]$$

です。ただし $s < -3N$ や $s > 3N$ は存在しないので、範囲を絞って計算します。

計算量

• 状態数は $M = \max S - \min S$ としたときに、 $O(N^2M)$。
• 各遷移は $M$ 通りなので、全体の計算量は $O(N^2M^2)$ で十分高速に実行可能です。

実装例を以下に示します。