表か裏かで遷移する動的計画法。 dp[i][j] := カードi,...,iまでの和をjにできるなら1、そうでないなら0
dp[i][j] = 1 の場合、以下の遷移をする。 - dp[i+1][i+a[i]] = 1 - dp[i+1][i+b[i]] = 1
dp[N][S]が1であればYes、そうでないならNo。
また、Yesの場合は、カードの置き方の一例を求める必要があるので、dpをNから逆順にたどっていく。
dp[N-1][S-a[i]] か dp[N-1][S-b[i]] でどちらかは1なので、前者であれば表を選び、後者であれば裏を選ぶ。
void solve(long long N, long long S, std::vector<long long> a, std::vector<long long> b){ vvl dp(N+9, vl(S+9, 0)); dp[0][0] = 1; REP(i, N) { REP(s, S) { if (dp[i][s]==0) continue; if (s+a[i]<=S) dp[i+1][s+a[i]] = 1; if (s+b[i]<=S) dp[i+1][s+b[i]] = 1; } } if (dp[N][S]) { cout << YES << endl; string ans; ll n = N; ll s = S; while (n > 0) { if (s >= a[n-1] && dp[n-1][s-a[n-1]]) { s -= a[n-1]; ans.push_back('H'); } else if (s >= b[n-1] && dp[n-1][s-b[n-1]]) { s -= b[n-1]; ans.push_back('T'); } n--; } reverse(ans.begin(), ans.end()); cout << ans << endl; } else { cout << NO << endl; } }