ゲームについて
- 典型
- grundy数
- 後退解析
- グラフとして捉える
グラフとして捉える
- 特定の条件のとき負ける・勝つを定義できる
- 後ろから考えてグラフのように把握する
例; 石取りゲーム
例; 偶数奇数で結果を判断できる
問題
解答
N = int(input())
A = [int(input()) for n in range(N)]
if all(a%2 == 0 for a in A):
print("second")
else:
print("first")
たかだか数回の有限の操作で最適に行き着ける
- 頻出例
- 偶数奇数の並びにできるか等の問題
- 円環状のグラフでモノが行き来する問題
例; マス目にコインが置かれているが、コインを移動することで偶数の目を最大化したい
問題
解説
- 縦に一回、横に一回動かすだけで最適解に行き着く
解答
H, W = map(int, input().split())
G = [list(map(int, input().split())) for h in range(H)]
ans = []
for h in range(H):
for w in range(W-1):
if G[h][w]%2 == 1:
G[h][w+1] += 1
G[h][w] -= 1
ans.append( (h, w, h, w+1) )
for h in range(H-1):
for w in range(W):
if G[h][w]%2 == 1:
G[h+1][w] += 1
G[h][w] -= 1
ans.append( (h, w, h+1, w) )
print(len(ans))
for rec in ans:
print(*[r+1 for r in rec])
例; 円環状の並びでアイテムを横の人に渡すとき、各々の人がかかる時間
問題
解説
- たかだか2回の操作ですべてのパターンが網羅できる(SからもらうかTからもらうかの２種類しかなくこれが確定するので)
解答
N = int(input())
*S, = map(int, input().split())
*T, = map(int, input().split())
L = [float("inf")]*N
for j in range(2):
for i in range(N):
L[i] = min(L[i-1] + S[i-1], T[i])
print(*L, sep="\n")