AtCoder Regular Contest 143 C,E問題メモ
C - Piles of Pebbles
問題
解法
Editorialを踏襲。
山を選んで石を取るゲームといえばGrundy数を使うNimが有名だが、これは2人の操作が同条件でないと使えない（はず）。
今回は先手と後手で取れる石の数が異なる。
ただ、考え方は似ていて、こういうゲームでは何らかの方法で「状態」を評価して、
「先手がいじった状態を、後手は必ず元に戻す方法があり、それを繰り返していくと先手が操作できなくなる」
みたいな法則がある場合が多い。
（もしくは、先手が先に操作することで、後手と先手を入れ替えて同様の展開に持ち込めるとか）
今回の場合、「同じ状態に戻せる」ような行動は何かと考えると、「先手が操作した山と同じ山を後手は選ぶと
各山の \mod{X+Y} は変わらない」というのは比較的思いつきやすい。
この方針で考えを進めるとして、各 A_i を X+Y で割ったあまりの数列を考える。
①全て X 未満
先手が操作した山を、後手は必ず操作できる。
後手が先手と同じ山の組を選び続けることで、後手必勝。
②X 以上の山が1つでもある
X \le Y か X \gt Y かで場合分けが発生する。
先手を太郎、後手を次郎とする。
②a:X \le Y
X \le Y の場合、先手太郎は X 以上の山を全て取るのがよい。すると、全ての山のあまりは Y 未満となる。
その状態で次郎からゲームが始まったと考えると、
全ての山が Y 未満の状況は先手である次郎から見ると①の状態となり、後手（＝入れ替える前の先手）である太郎が必勝。
②b:X \gt Y
X \gt Y の場合、少し思考が深くなる。
あまりの数列の値は3種類ある。
(1) X 以上 X+Y 未満
(2) Y 以上 X 未満
(3) Y 未満
先手太郎の操作後、次郎からゲームが始まったと考えると、①または②a のいずれかの状態になる。
太郎としては自分が必勝の①の状態に持ち込みたい。
そのためには、次郎に渡す段階で、Y 以上の山が1つもあってはいけない。
Y 以上の山を1つでも残して渡してしまったら、②aの状態になり太郎は負ける。
(1)は全て選ぶことで Y 未満にでき、(3)はもとから Y 未満なので、(1)と(3)しかなければ①になり太郎（先手）必勝。
逆に (2) が1つでもあったら、取ろうと取るまいと Y 以上となることを避けられず、②a の状態になるので、次郎（後手）必勝となる。
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
def solve(n, x, y, aaa):
xy = x + y
exists_ge_x = False
for i in range(n):
aaa[i] %= xy
if aaa[i] >= x:
exists_ge_x = True
if not exists_ge_x:
return 'Second'
exists_ge_y = False
for i in range(n):
if aaa[i] >= x:
aaa[i] -= x
if aaa[i] >= y:
exists_ge_y = True
if not exists_ge_y:
return 'First'
return 'Second'
n, x, y = map(int, input().split())
aaa = list(map(int, input().split()))
ans = solve(n, x, y, aaa)
print(ans)
|
E - Reversi
問題
N 頂点の木が与えられる
各マスにはリバーシの石が1つずつ置かれており、白黒どちらの面が表になっているかも与えられる
以下の操作を繰り返す
上手く操作順を決めることで全ての石を取り除くことが可能か判定せよ
可能な場合は、取り除く石の頂点番号を順に並べた数列のうち、辞書順最小のものを求めよ
1 \le N \le 2 \times 10^5
解法
葉から決める。
葉の頂点は、隣接頂点が1つだけ。
葉の頂点を u、その唯一の隣接頂点を v として、
この2つのどちらを先に操作しなければならないかは、u の色によって一意に決まる。
① ②
： ：
v ◎ ◎先
｜ ｜
u ○先 ●
すると、次は u を取り除いたグラフ上で同じ問題が解ければよくなる。
①の場合は v をひっくり返した状態を、新しいグラフ上での初期状態とする。
葉を取り除くことで新たに葉となる頂点が生まれたりして、これはグラフが1頂点になるまで繰り返せる。
最終的に残った1頂点が黒となってしまったら不可能。
白だったら可能となる。
辞書順最小の操作順を考える。
前述の操作によって、各辺につき「a は b より先に操作しなければならない」という条件が1個ずつ、計 N-1 個できている。
この条件を全て満たせば、必ず全ての石を取り除ける。
トポロジカルソートを行えばよい。
「自身より先に操作しなければならない頂点がない頂点」は、初手から自由に選べる。
これを最初の候補として、この中から1個ずつ選び操作を確定させていき、順次「自身より先に操作しなければならない未操作の頂点がなくなった頂点」を候補に加えていけば、適切な操作順を構築できる。
そのとき、候補が複数あったらheapqを使って小さい順に取り出すことで、辞書順最小を達成できる。
葉から1個ずつ切り取っていくという解法はたまに見るが、これもそれで行けることになかなか気づけなかった。
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
from collections import deque
from heapq import heappop, heappush
n = int(input())
links = [set() for _ in range(n)]
degrees = [0] * n
for _ in range(n - 1):
u, v = map(int, input().split())
u -= 1
v -= 1
links[u].add(v)
links[v].add(u)
degrees[u] += 1
degrees[v] += 1
s = list(map('WB'.index, input()))
q = deque(i for i, d in enumerate(degrees) if d == 1)
in_degrees = [0] * n
outs = [[] for _ in range(n)]
root = -1
while q:
u = q.popleft()
if len(links[u]) == 0:
root = u
break
v = next(links[u].__iter__())
if s[u] == 0:
s[v] ^= 1
in_degrees[v] += 1
outs[u].append(v)
else:
in_degrees[u] += 1
outs[v].append(u)
links[v].remove(u)
if len(links[v]) == 1:
q.append(v)
if s[root] == 1:
print(-1)
exit()
q = [i for i, d in enumerate(in_degrees) if d == 0]
ans = []
while q:
u = heappop(q)
ans.append(u + 1)
for v in outs[u]:
in_degrees[v] -= 1
if in_degrees[v] == 0:
heappush(q, v)
if len(ans) < n:
print(-1)
else:
print(*ans)
|