判定問題の解き方

カードの置き方の一例を求める必要はなく、総和を \(S\) にすることができるかどうかさえ判定すればよいとします。この場合、次のような動的計画法で解くことができます。

\(\text{dp}[i][j] :=\) カード \(1, \dots, i\) のみを考えたとき、和を \(j\) にできるなら \(1\)、そうでないなら \(0\)

初期状態は \(\text{dp}[0][0] = 1, \text{dp}[0][x] = 0 \, (x \gt 0)\) であり、次のように遷移を行います。

全ての \(j\) について \(\mathrm{dp}[i + 1][j] := 0\) と初期化する。

\(\mathrm{dp}[i][j] = 1\) となるすべての \(j\) について以下の処理を行う。なお、\(a_i, b_i\) は \(0\)-indexed であるとする。

• \(j + a_i \leq S\) ならば \(\mathrm{dp}[i + 1][j + a_i] := 1\) とする。

• \(j + b_i \leq S\) ならば \(\mathrm{dp}[i + 1][j + b_i] := 1\) とする。

計算量は \(O(NS)\) です。

詳細は過去の ABC の解説を参考にしてださい。

参考 : ABC240C 解説

動的計画法で求めた解の復元

実は、前述の \(\text{dp}[i][j]\) の情報のみから、カードの置き方の一例を求めることができます。

最後のカードに注目します。\(\text{dp}[N][S] = 1\) ということは、\(\text{dp}[N - 1][S - a_N]\) と \(\text{dp}[N - 1][S - b_N]\) の少なくとも片方は \(1\) です。このとき、

• \(\text{dp}[N - 1][S - a_N] = 1\) ならば、最後のカードを表を上に向けて置き、カード \(1, \dots, N -1\) の置き方をうまく決めることで、総和を \(S\) にすることができる。
• \(\text{dp}[N - 1][S - b_N] = 1\) ならば、最後のカードを裏を上に向けて置き、カード \(1, \dots, N -1\) の置き方をうまく決めることで、総和を \(S\) にすることができる。

これを繰り返すことで、カード \(N\)、カード \(N-1\)、\(\ldots\) の順番にどちらを上に向けて置くか求めることができます。

実装例 (C++)