D - Game in Momotetsu World

[hxrxchang]

https://atcoder.jp/contests/abc201/tasks/abc201_d

問題概要

H行W列のグリッドがある。グリッドの要素は + or -。
高橋君と青木君は順番に一つの駒を動かすゲームをする。
駒は最初グリッドの左上のマスにいる。
高橋君->青木君の順番で駒をグリッドの今いる要素の1個下or1個右に動かしていき、動かしたマスが+だったら1点獲得、- だったら1点マイナスされる。
両者が最適な行動をしたとき、どちらが勝つか求めよ。

解き方

高橋くん、青木くんそれぞれ最適に動いてDPをすればいいのでは？と考えたが、相手が自分にとって最適な動きをするわけがないので、それでは解けない。

2次元配列 dp[y][x] を、マス(y, x)にいるときの、高橋君の得点- 青木君の得点 の最適値として求めてゆく。
高橋くんは最大化、青木君は最小化させるべく行動していく。
このような解き方をミニマックス法という。

func solve() {
	in := getInts()
	h, w := in[0], in[1]
	grid := make([][]string, h)
	for i := 0; i < h; i++ {
		grid[i] = strToSlice(getStr(), "")
	}

	// dp[y][x] = (y, x)にいるときの、高橋君の得点 - 青木君の得点の最適値
	// 高橋君は最大化、青木君は最小化しようとする
	dp := make([][]int, h)
	visited := make([][]bool, h)
	for i := 0; i < h; i++ {
		dp[i] = make([]int, w)
		visited[i] = make([]bool, w)
	}

	ans := dfs(0, 0, h, w, grid, &dp, &visited)
	if ans > 0 {
		fmt.Println("Takahashi")
	} else if ans < 0 {
		fmt.Println("Aoki")
	} else {
		fmt.Println("Draw")
	}
}

func dfs(y, x, h, w int, grid [][]string, dp *[][]int, visited *[][]bool) int {
	if (*visited)[y][x] {
		return (*dp)[y][x]
	}
	(*visited)[y][x] = true

	if y == h-1 && x == w-1 {
		return 0
	}

	turn := (y + x) % 2

	if turn == 0 {
		// 高橋君のターン
		(*dp)[y][x] = MINIMUM
		if y+1 < h {
			var nextY int
			if grid[y+1][x] == "+" {
				nextY = 1
			} else {
				nextY = -1
			}
			(*dp)[y][x] = max((*dp)[y][x], dfs(y+1, x, h, w, grid, dp, visited) + nextY)
		}
		if x+1 < w {
			var nextX int
			if grid[y][x+1] == "+" {
				nextX = 1
			} else {
				nextX = -1
			}
			(*dp)[y][x] = max((*dp)[y][x], dfs(y, x+1, h, w, grid, dp, visited) + nextX)
		}
	} else {
		// 青木君のターン
		(*dp)[y][x] = BIGGEST
		if y+1 < h {
			var nextY int
			if grid[y+1][x] == "+" {
				nextY = -1
			} else {
				nextY = 1
			}
			(*dp)[y][x] = min((*dp)[y][x], dfs(y+1, x, h, w, grid, dp, visited) + nextY)
		}
		if x+1 < w {
			var nextX int
			if grid[y][x+1] == "+" {
				nextX = -1
			} else {
				nextX = 1
			}
			(*dp)[y][x] = min((*dp)[y][x], dfs(y, x+1, h, w, grid, dp, visited) + nextX)
		}
	}

	return (*dp)[y][x]
}

https://atcoder.jp/contests/abc201/submissions/61656809

[hxrxchang]

https://blog.hamayanhamayan.com/entry/2021/05/15/235741
https://note.com/igasu_7/n/ne9343ec03e19