ABC 201-D
について、例題1を使って解説します。
※ 簡単な DP であれば解ける前提での解説になります。
以下のように + または - が書かれた盤面があります。
初めに左上のマスにコマがある状態から、Takahashi くんと Aoki くんが交互に右または下にコマを動かしていきます。動かした先が + であれば、動かした人の得点が +1 され、- であれば -1 されます。先手は Takahashi くんです。
両者が最適に動かせば、どちらが勝つか、あるいは引き分けるかは開始時点で決定しているので、それを答える問題になります。
ちょっと実験してみると、Takahashi/Aoki くんのターン開始時点で存在しうるマスは重複しないことがわかると思います。
※ 問題文中の赤マス・青マスとは違った意味で使っています。混乱を招いたらすみません…。
勝敗にしか興味がない(=それぞれ何点になるかは求めなくて良い)ので、Takahashi - Aoki の点数だけ考えれば良いです。
そうすると、以下のようにして点差だけを考えることができます。
- 赤マスの
+は +1 - 赤マスの
-は -1 - 青マスの
+は -1 - 青マスの
-は +1
ここで、「最適な動き方」がどうなるかを考えると、
- もし赤マスにいれば、「右に動いた場合」と「左に動いた場合」の点差が大きくなる方を選ぶ
- もし青マスにいれば、「右に動いた場合」と「左に動いた場合」の点差が小さくなる方を選ぶ
という動かし方となります。
なので、「右のマスからゲームを開始した場合、最終的に点差がいくつになるか」と「下のマスからゲームを開始した場合、最終的に点差がいくつになるか」がもとまっていれば、そこに移動先のマスの数字を加算することで「このマスからゲームを開始した場合、最終的な点差がいくつになるか」を算出することができそうなので、以下のようなテーブルを埋めていくことを考えていきます。
一番考えやすいのは「右下のマス(=ゴール)から開始した場合」で、この場合はどちらもコマを動かせずにゲームが終了するので、点差は 0 となります。
次に、ゴールの1つ上のマスを考えます。
右には動けないので下に動くしかなく、そのとき点差は +1 されるので、ここには 1 が入ります。
同様に、ゴールの左のマスにいる場合も、右にしか動けず 1 が入ります。
では次に、真ん中のマスにいる場合を考えます。
真ん中のマスは赤マスなので、ここにいるということは Takahashi くんのターンです。したがって、右か下のどちらか最終的な点差の大きくなる方に動きます。
右に動くと、+1 されて、そこからの点数の変動は +1 になることがわかっています。
下に動くと、+1 されて、そこからの点数の変動は +1 になることがわかっています。
なので、どちらに動いても結果は同じで、このマスには 2 が入ることがわかります。
同じ要領で、中段左のマスを考えます。
ここは青マスなので、Aoki くんのターンです。したがって、右か下のどちらか最終的な点差の小さくなる方に動きます。
右に動くと +1 されて、そこからの点数の変動は +2 になることがわかっているので、右に動いた場合、最終的には +3 で終了します。
下に動くと -1 されて、そこからの点数の変動は 0 になる(交互に右に動くしかない)ので、下に動いた場合、最終的には -1 で終わります。
以上から、ここにいる場合は必ず下に動くことがわかり、その場合の最終的な点数は -1 になります。
あとは同じ要領で他のマスを埋めていきます。
最終的には以下のようになります。
この結果から、スタート地点から開始した場合、+2でゲームが終了することになるので、勝者は Takahashi くんであることがわかります。
上記の手続きをコードに落とし込むと AC です。
package main
import (
"bufio"
"fmt"
"io"
"os"
"strconv"
)
func main() {
solve(os.Stdin)
}
var dp [][]int
var field [][]int
var h, w int
func solve(r io.Reader) {
sc := initScanner(r, bufio.ScanWords)
h, w = sc.NextInt(), sc.NextInt()
dp = make([][]int, h)
field = make([][]int, h)
for i := 0; i < h; i++ {
dp[i] = make([]int, w)
field[i] = make([]int, w)
}
for i := 0; i < h; i++ {
l := sc.NextStr()
for j := 0; j < w; j++ {
sig := l[j]
if (i+j)%2 == 0 {
if string(sig) == "+" {
field[i][j] = -1
} else {
field[i][j] = 1
}
} else {
if string(sig) == "+" {
field[i][j] = 1
} else {
field[i][j] = -1
}
}
}
}
for i := h - 1; i >= 0; i-- {
for j := w - 1; j >= 0; j-- {
mayUpdate(i, j)
}
}
result := dp[0][0]
if result == 0 {
fmt.Println("Draw")
} else if result > 0 {
fmt.Println("Takahashi")
} else {
fmt.Println("Aoki")
}
}
func mayUpdate(curH, curW int) {
if curH == h-1 && curW == w-1 {
return
}
if curW >= w-1 {
dp[curH][curW] = dp[curH+1][curW] + field[curH+1][curW]
return
}
if curH >= h-1 {
dp[curH][curW] = dp[curH][curW+1] + field[curH][curW+1]
return
}
var (
right = dp[curH][curW+1] + field[curH][curW+1]
down = dp[curH+1][curW] + field[curH+1][curW]
)
if (curH+curW)%2 == 0 {
// Takahashi のターン
dp[curH][curW] = max(right, down)
} else {
// Aoki のターン
dp[curH][curW] = min(right, down)
}
}
type scanner struct {
sc *bufio.Scanner
}
func initScanner(r io.Reader, split bufio.SplitFunc) *scanner {
sc := bufio.NewScanner(r)
sc.Buffer(make([]byte, 1e7), 1e7)
sc.Split(split)
return &scanner{
sc: sc,
}
}
func (s *scanner) NextInt() int {
s.sc.Scan()
val, err := strconv.Atoi(s.sc.Text())
if err != nil {
panic(err)
}
return val
}
func (s *scanner) NextStr() string {
s.sc.Scan()
return s.sc.Text()
}