AtCoder Typical DP Contest - B「ゲーム」

シェアする

  • このエントリーをはてなブックマークに追加

「いやこれ分かんないよ」

「ん? 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; を忘れてて範囲外アクセスのエラー出しちゃった」

「うん、良いね。テストケースも合うし、これで提出しよう」

「やったー! AC!」

「おめでとう。」

「いやー、DPって難しいね、お兄ちゃん」

「だね。でも、前回と今回で、シンプルなDPは一通り理解できたはずだから、自力で解ける問題もあると思うよ」

「そうなんだ。じゃあABCのC問題あたりで過去問を探してみようかなあ」

「@Ymgch_K さんが作ってくれた AtCoder Finder というサイトで "動的計画法" で検索すると、DP問題が出てくるよ。方針のネタバレにはなるけど」

「おー、すごいねそのサービス」

「ちょっとずつ練習していけばいいよ」

「でもちょっと気になるからTDPCのC問題も見てみようっと」

「C問題は、あー、これかぁ」

「ちょっと! また全然雰囲気が違う問題なんだけど! なんでちょっと発展みたいな流れになってないの!」

「色んなジャンルの典型DPを扱うのがTDPCの思想みたいだから……」

「また今度教えてよね!」

「いいけど、まずは自力で解こうとしてみようね」

スポンサーリンク
レクタングル(大)
レクタングル(大)

シェアする

  • このエントリーをはてなブックマークに追加

フォローする