A - Tiny Arithmetic Sequence
https://atcoder.jp/contests/abc201/tasks/abc201_a
- ソートして、条件確認して、終わり
A_L = list(map(int, input().split()))
A_L.sort()
if A_L[1] - A_L[0] == A_L[2] - A_L[1]:
print('Yes')
else:
print('No')
B - Do you know the second highest mountain?
https://atcoder.jp/contests/abc201/tasks/abc201_b
- ソートして、2番目見て、終わり
N = int(input())
mount_L = []
for i in range(N):
S, T = input().split()
T = int(T)
mount_L.append([T, S])
mount_L.sort()
print(mount_L[-2][1])
C - Secret Number
https://atcoder.jp/contests/abc201/tasks/abc201_c
- 条件の数数えて、計算一発（n個のうち4個を選んで並び替え、みたいな）でもいける…はず(はまやん氏解説)
- 4桁の暗証番号は10000通りしかないので、そっちを全探索で条件満たしてる番号をカウントすれば良し
S = input()
ans = 0
for n in range(10000):
check_L = [0] * 10
for c in str(n).zfill(4):
c = int(c)
check_L[c] = 1
for i in range(10):
if check_L[i] == 1:
if S[i] == 'x':
break
else:
if S[i] == 'o':
break
else:
ans += 1
print(ans)
D - Game in Momotetsu World
https://atcoder.jp/contests/abc201/tasks/abc201_d
- 大嫌いな、所謂 #ゲームDP
- 最終盤面から1手ずつ戻す方向で考える
- #再帰関数 で書くと書きやすい、の意味が少しだけわかった気はする
- 無難にDPで最終盤面から埋めていくのが正解、かも、しれない…？
- Pythonが再帰関数に弱いため
- テーブルのDPやら、スタックの再帰やら、そのうち色々と別解実装する #TODO
import pypyjit
import sys
pypyjit.set_param('max_unroll_recursion=-1')
sys.setrecursionlimit(10 ** 6)
H, W = map(int, input().split())
grid_L = [input() for i in range(H)]
inf = 10 ** 18
memo = [[inf] * W for i in range(H)]
score = 0
def dfs(r, c):
if r == H - 1 and c == W - 1:
return 0
if memo[r][c] != inf:
return memo[r][c]
if (r + c) % 2 == 0:
# 高橋くんのターン
ret = -10 ** 18
if r + 1 < H:
if grid_L[r + 1][c] == '+':
ret = max(ret, dfs(r + 1, c) + 1)
else:
ret = max(ret, dfs(r + 1, c) - 1)
if c + 1 < W:
if grid_L[r][c + 1] == '+':
ret = max(ret, dfs(r, c + 1) + 1)
else:
ret = max(ret, dfs(r, c + 1) - 1)
else:
# 青木くんのターン
ret = 10 ** 18
if r + 1 < H:
if grid_L[r + 1][c] == '+':
ret = min(ret, dfs(r + 1, c) - 1)
else:
ret = min(ret, dfs(r + 1, c) + 1)
if c + 1 < W:
if grid_L[r][c + 1] == '+':
ret = min(ret, dfs(r, c + 1) - 1)
else:
ret = min(ret, dfs(r, c + 1) + 1)
memo[r][c] = ret
return ret
ans = dfs(0, 0)
if ans == 0:
print('Draw')
elif ans > 0:
print('Takahashi')
else:
print('Aoki')
E - Xor Distances
https://atcoder.jp/contests/abc201/tasks/abc201_e
- 根っこ決めて#BFS して、結果をもっちょもっちょと後処理集計する話
- 木の最短パスは #LCA #TIPS
- とりあえず頂点を1つ根っこにして植えてあげたい
- 1度根っこから #BFS しておけば、どの組み合わせも見れますね。素敵。
- とりあえず頂点を1つ根っこにして植えてあげたい
- 全部の$i,j$の組み合わせを探したいけど$(2\times10^5)^2$が通らないので、さてどうしよう問題
- #XOR はbit毎に見ろ #TIPS
- bit毎に見ていくと、0/1の2択でグルーピングできます
- 根からの距離が0の頂点→1の頂点の数だけ、2^iが答えに加算される
- 後はbit毎に愚直に数えていくイメージ
- 結局やってることは #全探索 の高速化感ありますね…
- 最後のbit操作回りはきれいに書けたと思う。ヨシ！
from collections import defaultdict, deque
mod = 10 ** 9 + 7
N = int(input())
edge_L = [[] for i in range(N)]
weight_d = defaultdict(int)
for i in range(N - 1):
u, v, w = map(int, input().split())
u -= 1
v -= 1
edge_L[u].append(v)
edge_L[v].append(u)
weight_d[(u, v)] = w
weight_d[(v, u)] = w
inf = 10 ** 18
dist_L = [inf] * N
dist_L[0] = 0
que = deque([0])
while que:
now_pos = que.popleft()
for nex_pos in edge_L[now_pos]:
if dist_L[nex_pos] != inf:
continue
dist_L[nex_pos] = dist_L[now_pos] ^ weight_d[(now_pos, nex_pos)]
que.append(nex_pos)
ans = 0
for i in range(60):
cnt = [0, 0]
for dist in dist_L:
cnt[(dist >> i) & 1] += 1
ans += (1 << i) * (cnt[0] * cnt[1])
ans %= mod
print(ans)