京セラプログラミングコンテスト2022 (AtCoder Beginner Contest 271) D - Flip and Adjust (400)
$ dp[i][j] で$ i番目までのカードで和を$ jに可能かを表す
これは一つ前のカードの結果から遷移することで$ \mathcal{O}(NS)で可能
作れる場合は後ろからDPの復元をする
$ A_i,B_iの内、選んだ方で一つ前の結果も作成可能になっている方を選ぶ
両方可能ならどちらを選んでも良い
答えは文字列の後ろにつけていって最後に反転するのが楽