▲「いやこれ分かんないよ」
■「ん? AtCoder Typical DP Contest の B 問題『ゲーム』を考えてるの?」
▲「うん。この前お兄ちゃんにDPを教えてもらったけど、なんか A 問題と全然違うんだけど」
■「確かに、雰囲気は違うね。でも根本のDPとしての発想は同じだよ」
▲「えー、だってこれ、2人のプレイヤーがそれぞれの判断で行動するじゃん」
■「そうだね。どちらも自分の得点、つまり取った “物” の価値の和を最大化しようとするんだね」
▲「そもそもこれって、2人が目指すのは『自分の得点を増やすこと』なの? 『相手の得点を減らすこと』なの?」
■「それはね、同じことだよ」
▲「えっ! どういうこと?」
■「このゲームが終わったら、全ての “物” がどちらかのプレイヤーの所有になってるよね?」
▲「うん。どっちの山も空になるまで続けるんだもんね。”物” は勝手に消えたりしないし」
■「ということは、ゲーム終了時点での、2人の得点の合計はどうなる?」
▲「えーっと、あ! 全部の “物” の価値の合計になるんだ!」
■「そう。だから、『自分の得点を増やすこと』と『相手の得点を減らすこと』は同じになる」
▲「なるほどー、そういうことかー」
■「じゃあ、DPについて考えていこうか」
▲「いくぞー!」
■「まず、DPの基本的な考え方ってどんなんだっけ?」
▲「えっと、DPテーブルがあって、それを漸化式で更新するやつ?」
■「そんな感じだね。例えば dp[i][j] を、 dp[i-1][j] とか dp[i][j-1] とか、[i][j] よりも添字が小さいものだけを使って計算できたら、添字の小さい順に埋めて行けるよね」
▲「それで、DP[N][なんとか] みたいなのが答えになったりするんだよね」
■「そうだね、最後の値が答えになる場合があるね。でも、最初の dp[0][0] みたいなのが答えになる場合もあるんだよ」
▲「そうなの? 前から埋めていくんじゃないの?」
■「うん。例えば?dp[i][j] を、 dp[i+1][j] とか dp[i][j+1] とか、[i][j] よりも添字が大きいものだけを使って計算できる場合は、添字の大きい順に埋めて行かないといけない」
▲「そういう問題もあるんだね」
■「dp[i][j] とかには、値としては何が入るかな?」
▲「えっと、この前のは、” i 番目までで j を作れるか” だったよね。これを使って、” N 番目(全部)使って X を作れるか” みたいなのを、全部の X について調べたんだよね」
■「そうだね」
▲「ってことは、この dp[i][j] には、“元の問題に近いけど、スケールが小さい問題の答え” みたいなのが入ってるってことになるのかな?」
■「正解! DPテーブルには、部分問題の答えが入ってるんだね」
▲「部分問題?」
■「その問題の一部の範囲を対象にした、ちょっと小さい問題のことを、部分問題と言ってみた。正式な言葉かどうかは分からないけど」
▲「部分的な問題、元の問題を小分けにした問題ってことだね。ある部分問題の答えから、それよりもちょっと大きい部分問題の答えを計算する、っていうのを繰り返すのがDPかな?」
■「そうだね。そうして最終的に問題全体に辿り着くんだね」
▲「なるほどー、部分問題かぁ」
■「それと、DP テーブルの添字は何になる?」
▲「添字は、この前の場合は、”何番目まで使う場合” と “作りたい数字” だよね」
■「うん。この、特に “何番目まで使う場合” というのは、“状態” と言える」
▲「状態?」
■「” i 番目までがある状態” みたいな感じかな」
▲「数字がそもそも i 番目までしかない場合を考えるイメージだね。」
■「あるいは、” i 番目を使える状態” とか」
▲「状態ねぇ……」
■「状態は、“遷移” するんだ」
▲「状態が遷移? って移り変わるってことだよね」
■「そう。状態は、一手進めると別の状態に移る」
▲「この前言ってた、DAG? とかいうやつの話? あれはたしかに頂点から次の頂点に、矢印で移ってたけど」
■「うん。今回の問題では、とくに “状態と遷移” の考え方が大事になるんだ」
▲「うーん、よく分からないけど、とりあえず覚えとくよ」
■「さて、今回の問題について、整理してみよう」
▲「えっと、B問題『ゲーム』は、数列が 2 つ与えられて、2 人のプレイヤーが交互に先頭から数字を取っていくんだね。それで、最終的に “自分が取った数字の和” を大きくしたい」
■「そうだね。とりあえず、サンプルケースを実際にやってみると良いよ」
▲「サンプル 2 は大きいから、まずは 1 でやってみたよ」
■「サンプル 1 は、一つの山が A(1) 、もう一つの山が B(2, 10) だね」
▲「状態と遷移っていうの、なんとなく分かったかも。最初の状態は、A(1), B(2, 10) の状態だね。それが、1人目の行動によって、変化するって感じ?」
■「そうそう。その状態と遷移が重要なんだ」
▲「最初に A を取ると、あとは 2 回とも B を取らないといけなくなって、最初に B を取ると、次も選べるんだよね。そこから先は選べないから、合計で 3 通りの取り方があるんだね」
■「ABB, BAB, BBA だね。それぞれの場合で、結果はどうなった?」
▲「ABB は、2 人の得点が 先攻から順に [11, 2] になって最適だね」
■「うん」
▲「BAB は、[12, 1] だけど、後攻が 2 手目に A を選ぶってあり得ないよね」
■「なるほど」
▲「BBA は、[3, 10] で、後攻が勝っちゃうね」
■「そうだね。BAB はあり得ないって言ったけど、それはどうして?」
▲「だって、先攻が B から取った状態で、後攻は “A から取れば後攻負け、Bから取れば後攻勝ち” なんだよ? そりゃ、Bから取るでしょ」
■「良いね。そうしたら、最初に先攻が B を取るのはどうかな?」
▲「えっと、これもあり得ないよね。だって、最初に B から取ったら後攻の勝ちが確定するんだもん。後攻はわざと負けてくれないもんね」
■「そうだね。だから、先攻は絶対に A から取らないといけないんだ」
▲「先手勝ち確定の状態を赤、後手勝ち確定の状態を青で塗ると、こんな感じだよね」
■「そうだね。あり得ない遷移がさっき言った 2 つあって、それ以外の遷移は “その手前に到達したら絶対にその遷移をする” っていうことだよね」
▲「そうそう。赤い矢印を辿るはずだよね。でも、1 手目にどっちを取るかは、それぞれの遷移先でどっちが勝ち確定かが分からないと、決められないよね」
■「良いね。この色と赤矢印は、右端、つまりゲームの終了側から決まっていくんだね」
▲「うーん、なんかこの前のメモ化再帰を思い出す……」
■「どういうこと?」
▲「あれは、最後の ” 3 個まで使って 10 を作れるか?” っていうのを判定するのに、最初まで潜っていって、最初の側から 〇 か × かが決まっていって、最後に欲しかったところが埋まったんだよね」
■「そうだったね」
▲「今回は、最初の状態について “どっちに行くべきか” が知りたくて、でも、実際に分かるのは最後の方から順番なんだよね」
■「良い着眼点だね」
▲「あれ、でもこの前は “最後の値(作れるかどうか)を知りたいけど、分かるのは最初から” だったよね」
■「うん」
▲「でも今回は “最初の値(勝ち負け)が知りたいけど、分かるのは最後から” になるんだね。さっきもそんな話をしてたけど、これでも大丈夫なの?」
■「大丈夫だよ。最終的にDPテーブルを埋めるときに、今回は最後から順番に埋めていくことになる。ゲームの問題では、最後から決まっていくことが多いんだ」
▲「へー。じゃあ、ゲーム問題では決着の直前から考えていくのが良いんだね」
■「うーん、もちろん例外もあるし、後ろから見るのが正解だと思い込むのは良くないけど、最初の着眼点としては良いと思うよ」
▲「なるほどー」
▲「といっても、この問題まだ解けてないよね!」
■「そうだね。また状態数が2^(A+B)ぐらいだったね」
■「でもこの図の中に、同一視できる状態があるんだ」
▲「同一視? 違う状態なのに同じ状態として扱うってこと? そんなことして解けるの?」
■「解けるよ。DPのコツは同一視であるとも言えるんだ」
▲「同一視、同一視…… {Aの山, Bの山, 先攻の点数, 後攻の点数} の組み合わせは全部バラバラだから、まとめられないよね。でも、{Aの山, Bの山} なら同じのがいくつかあるね」
■「良いね。その図の黄色で囲った部分を、1つにまとめてみよう」
▲「こんな感じ? 点数はまとめられないから、とりあえず消したよ」
■「そうだね。状態数は 6 になったね。この 6 という数は、どこから来たか分かる?」
▲「どこからって、図を書いたらこうなったんだけど」
■「それはそうなんだけど、うーん、難しいな。とりあえず、この図の特徴が何かあれば言ってみて」
▲「そんな無茶振りみたいな…… えっと、始点と終点が 1 つずつ!」
■「他には?」
▲「うーん、斜めの長方形っぽい? でもこれは、終点が 1 つだから当たり前なのかな」
■「良い着眼点だよ。この図の斜めの矢印は、上がるのと下がるのがあるけど、それぞれに共通点はある?」
▲「上がるのは全部 A の山から取る遷移で、下がるのは全部 B の山から取る遷移だね!」
■「スタートからゴールまで、何回上がって何回下がる?」
▲「えーっと、どのルートを通っても 1 回上がって 2 回下がるね! ってこれ、A の山に物が 1 個あって、B の山に物が 2 個あるから当たり前じゃん!」
■「そうだね。じゃあ、スタートからゴールまでのルートは何通り?」
▲「 1 回上がって 2 回下がるから、” 3 回の移動のうち、どの 1 回で上がるか?” のパターン数と同じになって、3_C_1=3 通りになるやつだ!」
■「その通り。それって、長方形で角から角に行く最短経路の数の問題だよね」
▲「うん。組合せの例題で出てくるやつだよね」
■「じゃあ、この図もそんな感じに書き換えたくない?」
▲「書き換えって、こんな感じ?」
▲「うわ、すごく分かりやすくなった!」
■「さっきまでの図と比べると、裏返ってるから注意が必要だね。こうすると、左上の初期状態の名前を (0,0) として、右下の最終状態の名前を (1,2) とするような名前を付けたくなる」
▲「”付けたくなる” っていうのがちょっと引っかかるけど、なんとなくわかる気がする」
■「じゃあ、(i, j) の状態というのはどういう状態のことなのか、説明できる?」
▲「(i, j) は、下に i 回行って、右に j 回行くから、” A の山から i 個取って、B の山から j 個取った状態” だね!」
■「正解。じゃあ、これをDPテーブルとして解いてみよう!」
▲「解いてみよう! って言われてもなあ…… とりあえず、DPテーブルは二次元配列で、
dp[i][j] = ” A から i 個、B から j 個取った状態の何か”
って感じかなあ。何の値を入れたら良いんだろう…… スコア関係の値が入るんだよね」
■「最初の方の話を思い出してね。”自分の得点を増やす” と “相手の得点を減らす” は同じなんだよ。それは、合計得点が必ず一定の値になるからだったね」
▲「スコアは 2 人分あるから面倒なんだよね。でも、その考え方だと、先攻のスコアだけを見てもいいんだよね」
■「そうそう、良い感じ」
▲「じゃあ、“その状態での先攻のスコア” みたいな値を入れようかな」
■「更新のしかたはどうなる?」
▲「初期状態 (0,0) の値が 0 で、状態 (1,0) が 1 で、状態 (0,1) が 2 で、状態 (1,1) は…… あれ、どうなるの?」
■「後手の行動で先手の得点は増えないけど、(1,0) と (0,1) のどっちから (1,1) に来るのかが分からなくて困るよね」
▲「うーん、じゃあこれはダメかぁ」
■「さっきまでの考察を思い出してね」
▲「あ、そういえば、最後から見ていくと良いみたいな話があったね。だったら、最終状態 (1,2) で 0 になるような値を入れたらいいのかな」
■「その調子。考え方の順番がおかしいような気もするけど」
▲「さっきお兄ちゃんが部分問題みたいな話もしてたよね。ってことは “その状態から最終状態に行くまでに先攻が得るスコア” みたいなのを入れたらいいのかな」
■「おお、すごい」
▲「え、合ってる?」
■「もうちょっと考えてみよう」
▲「合ってるかぐらい教えてよー!」
■「まあまあ。その場合の部分問題は “初期状態が (i,j) の場合の問題” ということになるね。本来の問題よりも、物の数が減ってる」
▲「だね。これだと、最終状態は、物が無いから 0 点で引き分けだね。」
■「じゃあ、途中の状態 (i,j) からの移動を考えよう」
▲「手番が先行か後攻かで行動が変わるよね。状態 (i,j) で取れる行動は ” A から取る” と ” B から取る” だけど、先攻の場合は “先攻のスコアを大きくする” で、後攻の場合は “先攻のスコアを小さくする” ように行動するはず」
■「良いよ」
▲「状態 (i,j) のとき、A の山から取れるのは価値 a[i] のもの、B の山から取れるのは価値 b[j] のものだね」
■「うん」
▲「ということは、こんな感じかな?
手番が先攻なら:
dp[i][j] = max(a[i] + dp[i+1][j], b[j] + dp[i][j+1])
(Aから価値a[i]のものを取ると、状態(i+1,j)の場合の最適スコアにa[i]足したスコアが得られる。Bも同様)
手番が後攻なら:
dp[i][j] = min(dp[i+1][j], dp[i][j+1])
(後攻が物を取っても先攻のスコアは増えない。また、後攻は先攻スコアを最小化する)
」
■「良いね。合ってるよ。i==A や j==B の場合は、片方の行動しか取れないけど、それはまあ例外処理として後回しにしよう」
▲「後攻番の場合に取る物のスコアを考慮してないんだけど、これでも大丈夫だよね?」
■「うん。後攻は添字を進めることで “その物を先攻が取れないようにする” ということを実現しているんだ。」
▲「あと、これって、手番の情報が必要だから dp[i][j][手番] みたいにならないの?」
■「それはね、ならないよ。そうしても解けるけど、必要ないんだ。理由を考えてみて」
▲「さっきの図に、先攻番ならピンク、後攻番なら青を塗ると、こんな感じだね」
▲「綺麗に交互になってるね。あ、これって当たり前か。一手進むと i と j のどちらかが絶対に 1 増えて、手番が入れ替わるんだもんね」
■「どうやってこれを判定する?」
▲「 i が偶数なら、j が偶数の時に先攻番…… ってややこしいね。うーん、もっとうまい判定方法…… あ! i+j の偶奇で判定すれば良いんだ!」
■「そうだね。i と j のどちらかが 1 増える場合、i+j は必ず 1 増えるからね」
▲「じゃあ、こんな感じだね!」
if ((i + j) % 2 == 0){? // 先攻番
dp[i][j] = max(a[i] + dp[i+1][j], b[j] + dp[i][j+1])
} else {? // 後攻番
dp[i][j] = min(dp[i+1][j], dp[i][j+1])
}
■「完璧だ。これで、dp[0][0] が答えだね」
▲「ループ回すとき、逆順に回さないとダメだから注意しないとね。」
■「じゃあ、コーディングしてみよう」
▲「こんな感じだね! 最初 if (i == A && j == B) continue; を忘れてて範囲外アクセスのエラー出しちゃった」
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
#include <iostream> #include <vector> #include <algorithm> // std::max, std::min using namespace std; #define repr(i,a,b) for(int i=a;i<b;i++) #define rep(i,n) for(int i=0;i<n;i++) #define reprrev(i,a,b) for(int i=b-1;i>=a;i--) #define reprev(i,n) reprrev(i,0,n) int main(void) { // 入力受け取り int A, B; cin >> A >> B; vector<int> a(A), b(B); rep(i, A) { cin >> a[i]; } rep(i, B) { cin >> b[i]; } // 要素数[A+1][B+1]の二次元vectorを用意 // dp[i][j] = Aからi個、Bからj個取った状態から最後までの // 先攻の最適スコア vector<vector<int>> dp(A + 1, vector<int>(B + 1)); // 最終状態の値を0にする dp[A][B] = 0; // 逆順にループしてDPテーブルを埋める // ループ範囲は[A~0][B~0]なので、最後に注意!(A-1~0とかにならないように!) reprev(i, A + 1) { reprev(j, B + 1) { if (i == A && j == B) continue; // 最終状態はパスする if ((i + j) % 2 == 0) { // 先攻番 if (i == A) { // Aの山が空 dp[i][j] = b[j] + dp[i][j + 1]; } else if (j == B) { // Bの山が空 dp[i][j] = a[i] + dp[i + 1][j]; } else { // 先攻は先攻スコアを最大化 dp[i][j] = max(a[i] + dp[i + 1][j], b[j] + dp[i][j + 1]); } } else { // 後攻番 if (i == A) { // Aの山が空 dp[i][j] = dp[i][j + 1]; } else if (j == B) { // Bの山が空 dp[i][j] = dp[i + 1][j]; } else { // 後攻は先攻スコアを最小化 dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]); } } } } // 初期状態での先攻スコアが出力 cout << dp[0][0] << endl; return 0; } |
■「うん、良いね。テストケースも合うし、これで提出しよう」
▲「やったー! AC!」
■「おめでとう。」
▲「いやー、DPって難しいね、お兄ちゃん」
■「だね。でも、前回と今回で、シンプルなDPは一通り理解できたはずだから、自力で解ける問題もあると思うよ」
▲「そうなんだ。じゃあABCのC問題あたりで過去問を探してみようかなあ」
■「あまり急がず、ちょっとずつ練習していけばいいよ」
▲「でもちょっと気になるからTDPCのC問題も見てみようっと」
■「C問題は、あー、これかぁ」
▲「ちょっと! また全然雰囲気が違う問題なんだけど! なんでちょっと発展みたいな流れになってないの!」
■「色んなジャンルの典型DPを扱うのがTDPCの思想みたいだから……」
▲「また今度教えてよね!」
■「いいけど、まずは自力で解こうとしてみようね」