communication-easy

解説

問題の整理

$N$ 回の選択があり、$i$ 回目には $K_i$ 個の選択肢が存在します。
各選択肢にはスコア $S_{i,j}$ が割り当てられており、それを選ぶと コミュニケーションポイント に $S_{i,j}$ が加算されます。

最終的にポイントの合計が $X$ 以上になる選び方の総数を求める問題です。

総選択肢数は

$$\prod_{i=1}^{N} K_i$$

通りあります。制約から $K_i \leq 4$, $N \leq 10$ なので、高々 $4^{10} = 1,048,576$ 通りであり、十分に全探索が可能です。

解法方針

次のような方法で解くことができます。

1. 全てのパートの選択肢を直積で列挙する。

2. 各組み合わせの合計スコアを計算し、$X$ 以上ならカウントする。

計算量

$O(K^N)$ で制約下で十分高速に動作します.

実装例は以下のようになります。