ABC201 D 解答

D - Game in Momotetsu World（1317）

問題

D - Game in Momotetsu World

問題文

H 行 W 列のマス目があり、各マスは青マスまたは赤マスのどちらかです。上から i 番目、左から j 番目のマスは、Ai, j が + なら青マスであり、- なら赤マスです。
最初、このマス目の一番左上のマスに一つ駒が置かれていて、高橋君と青木君はこの駒を使ってゲームをします。
2 人の得点は最初 0 点ずつです。2 人は、高橋君から始めて交互に次の操作をします。

・駒を一つ右または一つ下のマスに動かす。ただし、駒がマス目の外に出るような動かし方はできない。動かした人は、駒の移動後のマスが青マスなら
1 点を得て、赤マスなら 1 点を失う。

どちらかが操作できなくなった時点でゲームは終了します。ゲームの結果は、終了時の 2 人の得点が異なるならば得点の大きい方が勝ち、同じならば引き分けとなります。
両者とも自分の勝敗が最適になるように行動したとき、ゲームの結果を求めてください。

制約

1 ≤ H, W ≤ 2000
Ai, j は + または -

考察

ゲームをする問題です。いきなりですがゲーム問題で大切なのは

後ろから考える

という点です。これを行うとゲームにおいて扱いずらい

両者が最適な行動をとる

という条件を満たすことが可能となります。

ですが、まずは両者の得点の扱い方についての説明します。本問題大切なのは高橋君と青木君のどちらが勝利するか（もしくは同点か）を判断することです。ですので、高橋君のや青木君の得点は無視しても大丈夫です。もう少し言い換えるなら

高橋君と青木君のスコアの差

さえ管理できていれば十分です。これも様々な考え方があると思いますが、今回は高橋君を主体に考えてみましょう。どうやら盤面には「+」と「-」のマスがあり、高橋君と青木君が交互に取るみたいです。もし、高橋君が「＋」のマスに止まれば当然＋１点、「ー」のマスに止まればー１点です。さて、ここで青木君のターンになったとしましょう。青木君が「＋」のマスに止まりますと、高橋君は勝利から遠ざかってしまいますのでこちらはー１点、逆に青木君が「ー」のマスに止まりますと高橋君にとってはそれは＋１とみなすことができます。

このように

高橋君にとってどうなのか

という情報を管理すれば、両者のスコアの差は表現でき、本問題を解くのに必要な値を得ることが可能です。

これで、スコアの説明はおしまいです。続いて、ゲーム問題について説明をしていきます。

ゲーム問題を考えるときに最も扱いにくいのが、先にも書いた

両者が最適な行動をとる

という条件です。最適な条件って何なんでしょうね。

次のマスが「＋」の方？でも一回「ー」を踏めばあとは「＋」で得点をいっぱい稼げるなあ、ボーナスタイムだ！

など色々な要素が考えられてしまいます。そうです。色々な要素を考えなければいけないからダメなのです。わかんなくなってしまいます。ということで、まずはとっても簡単な例を示してみましょう。2*2でゲームをします。

先攻は高橋君なので、高橋君が動かすときにいるマスを赤、青木君のマスを水色にしています（わかりにくくてすみません、結局のところ高橋君が取る点数が水色、青木君が取る点数は赤色のマスの記号になります。）。交互に手番が来ますので、縦と横のマスの和の偶数、奇数で手番は判断できます。

ですので、上記の高橋君の立場になってみると以下のような得点となります。

赤＋：ー１
赤ー：＋１
水色＋：＋１
水色ー：ー１

わかりにくくてすみませんがこのようになります。このくらい盤面が小さかったらどっちが勝つか、どのように行動するのが最適化は一目瞭然ですね。高橋君が右に移動するのが最適です。残念ながら青木君には選択肢はありません。

上記の得点票で計算すると＋２ですね。2点ほど高橋君の得点が高くなるみたいです。

ここで、以下を考えます

そのマス以降であと何点獲得できるか（そのマスは含まない）

です。これを書き込んであげましょう。

値の算出は右下からです。右下にいるときはもうこれ以上進めませんので、獲得できる特典もありませんね。０となります。このマスの「赤いー」はカウントしないことに注意です。このマス以降です。

次に左下です。この場合には選択肢はありませんね。右に進むしかありません。ですので、右下の「赤いー」だけ得点が可能なので、＋１を書き込みます。右上も同様です。

最後に左上です。この値の算出には

誰の手番か

がとても大きく関わってきます。今回は高橋君の番です。右上、左下ともにそれ以降に獲得できるスコアは＋１となっています。ですが、そのマスにて獲得できる得点が異なります。もし、右に進んだ場合には右上の「赤のー」の＋１とそれ以降の＋１の合わせて＋２点が獲得できることになります。一方で、下に進んだ場合には「青いー」のー１とそれ以降の＋１で合わせて 0 点を獲得できます。繰り返しますが、現在の手番は高橋君です。賢い高橋君はどちらに道を選択するでしょうか。

当然、右側ですね。右に進めばより大きな得点が獲得できるのですから。ということで、左上の数字は右と下のより大きい数字に更新されます。

このようにすることで最適な行動を選択できます。

今回は高橋君にだけ選択肢がありました。ちょっと不公平ですね。別の盤面で青木君の選択肢も見てみましょう。サンプルの１となります。前の盤面とは違うので注意です。

一番左の真ん中の「青い＋」のマスを見ましょう。電卓で言うところの４の場所です。この場所の更新を考えます。もし右に行くとすると、そのマスの「赤いー」で＋１点とそれ以降の＋２の合計で＋３点獲得できます。一方で、下に行くと「赤い＋」でー１点とそれ以降の０点の合計でー１点獲得できます。

そして、今回の手番は青木君です。青木君が勝つためにはどんどん得点を小さくする必要があります。ですので、青木君は下に行くわけです。ということで2つの値の最小値であるー１に更新されます。

これを繰り返していくと次のような図になります。

開始点である左上の値に注目すると、その値は正ですね。ということはこの地点から両者が最適に行動すると＋２点獲得されるということです。ですので、この盤面では高橋君の勝利です。

なんとなくイメージが掴めたのでしょうか。この方法で大切な考え方は

後ろからやることで、その地点以降で獲得される得点が決定される

ということです。盤面が大きい場合、開始点から考えると、考慮すべき要素が多すぎて計算できませんが、小さい盤面ならその地点に到達した時点で、それ以降の得点が全部確定されます。その盤面を少しずつ拡張していくことにより大きな盤面でも対応することが可能となります。

以上の考えをまとめます。

１）後ろから「それ以降に何点獲得できるか」を計算する
２）高橋君の番：次のマスとそれ以降マスの得点の和の大きいほうで更新
３）青木君の番：次のマスとそれ以降マスの得点の和の小さいほうで更新
４）左上になるまで行う
５）左上の正負により勝敗を決定する

以上で考察は終了です。少し実装が大変ですが、あとはコメントにて補足します。

実装

 #include <bits/stdc++.h> #define  rep(i,n) for(int i=0;i<n;++i) #define  reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<ll, ll>;

int main()
{
	int h, w;
	cin >> h >> w;
	vector<string> A(h);
	rep(i, h) cin >> A[i];
	vector<vector<int>> dp(h + 5, vector<int>(w + 5));
	const int INF = 1e9;
	for (int y = h - 1; y >= 0; --y)
	{
		for (int x = w - 1; x >= 0; --x)
		{
			//右下のマスにいるときは計算しない
			if (x == w - 1 && y == h - 1) continue;
			//手番の計算
			bool Takahashi = false;
			if ((x + y) % 2 == 0) Takahashi = true;
			//dp1は右移動のマスの値
			//dp2は下移動のマスの値
			int dp1, dp2;
			//範囲外のときはこの値で更新しないようにする
			if (x + 1 >= w)
			{
				//高橋君のときは最大値で更新するため
				//-INFを入れる
				dp1 = INF;
				if (Takahashi) dp1 *= -1;
			}
			else
			{
				//範囲内のとき
				if (Takahashi)
				{
					//今のマスが高橋君の番
					//次のマスの+は＋１、-は-1
					dp1 = dp[y][x + 1] + (A[y][x + 1] == '+' ? 1 : -1);
				}
				else
				{
					//今のマスが青木君の番
                   //次のマスの+は-１、-は+1
					dp1 = dp[y][x + 1] + (A[y][x + 1] == '+' ? -1 : +1);
				}
			}
			//縦移動も同様に行う
			if (y + 1 >= h)
			{
				dp2 = INF;
				if (Takahashi) dp2 *= -1;
			}
			else
			{
				if (Takahashi)
				{
					dp2 = dp[y + 1][x] + (A[y + 1][x] == '+' ? 1 : -1);
				}
				else
				{
					dp2 = dp[y + 1][x] + (A[y + 1][x] == '+' ? -1 : 1);

				}
			}

			//更新
			if (Takahashi)
			{
				//高橋君：最大値
				dp[y][x] = max(dp1, dp2);
			}
			else
			{
				//青木君：最小値
				dp[y][x] = min(dp1, dp2);
			}
		}

	}
	//結果判定
	if (dp[0][0] > 0) cout << "Takahashi" << endl;
	else if (dp[0][0] < 0) cout << "Aoki" << endl;
	else cout << "Draw" << endl;
	return 0;
}

あとがき

少しだけ補足です。他の方の解法を見ると、各マスの値は

そのマスとそれ以降のマスの得点の合計

としているものが見られました。この場合も基本は同じですが、左上のマスの計算が必要になります。色々な方の記事を見比べる場合にはこの点の違いに注意してください。

ゲームの問題でした。

方針といいますか定石といいますか、を知らないと一歩目を踏み出しにくいと思います。大切なのは

後ろから考える

ということです。繰り返しとなりますが、これにより最適な行動が決定されます。

慣れるまではかなり難しいと思います。私も偉そうに記事を書いていますが、コンテスト中にACしたのはこの問題が初めてです。後ろからとはいうものの、どうやって遷移させるかなどを考えるのは頭がこんがらがります。通常のDPの遷移に慣れておく必要もあります。ですので、自分の手を動かして数をこなすことが大切だと思います。様々な問題に挑戦するうちに、少しずつそのような思考過程ができるようになるはずです。

本当に難しいと思います。難しかったです。ですので解けたらたくさん喜びましょう。

最後に典型90問となりますが類題を載せておきます。「Grundy数」という別の要素が加わっていますが、この問題の一山当たりの勝敗を求めてみるといい練習になると思います。それだけなら「Grundy数」を知らなくても大丈夫です。

031 - VS AtCoder（★6）