AtCoder Beginner Contest 213
A - Bitwise Exclusive Or
import sys
import heapq, math
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right
inputs = sys.stdin.readline
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)
def main():
a,b = map(int, inputs().split())
for c in range(0, 256):
if a^c==b:
print(c)
exit()
if __name__ == '__main__':
main()
cの範囲が狭いので、この範囲で全探索すれば十分
B - Booby Prize
import sys
import heapq, math
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right
inputs = sys.stdin.readline
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)
def main():
n = int(input())
a = list(map(int, inputs().split()))
d = {e+1:x for e,x in enumerate(a)}
d = sorted(d.items(), key=lambda x:x[1], reverse=True)
print(d[1][0])
if __name__ == '__main__':
main()
ソートした後2番目のスコアを参照する
C - Reorder Cards
import sys
import heapq, math
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right
inputs = sys.stdin.readline
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)
def main():
h,w,n = map(int, inputs().split())
idx, y, x = [], [], []
for _ in range(n):
a,b = map(int, inputs().split())
y.append(a)
x.append(b)
idx.append((a,b))
x = sorted(list(set(x)))
y = sorted(list(set(y)))
dx,dy = {xx:e+1 for e,xx in enumerate(x)}, {yy:e+1 for e,yy in enumerate(y)}
for (a,b) in idx:
print(dy[a], dx[b])
if __name__ == '__main__':
main()
座標圧縮を行う。行・列ともに{座標:何番目か}のインデックスを持つ
同じ座標を消去した後に順番を決めることに注意
D - Takahashi Tour
import sys
import heapq, math
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right
inputs = sys.stdin.readline
mod = 10**9+7
inf = float('inf')
sys.setrecursionlimit(10**7)
ans = []
def main():
def dfs(pos, pre):
ans.append(pos)
for nx in v[pos]:
if nx!=pre:
dfs(nx, pos)
ans.append(pos)
n = int(input())
v = [[] for _ in range(n+1)]
for _ in range(n-1):
a,b = map(int, inputs().split())
v[a].append(b)
v[b].append(a)
for x in v:
x.sort()
dfs(1,-1)
print(*ans)
if __name__ == '__main__':
main()
dfsによるオイラーツアーを行う。
再帰なのでsys.setrecursionlimit(10**7)を忘れずに設定する
E - Stronger Takahashi
import sys
import heapq, math
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right
inputs = sys.stdin.readline
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)
def main():
h,w = map(int, inputs().split())
g = [list(input()) for _ in range(h)]
cnt = [[inf]*w for _ in range(h)]
que = deque([(0,0,0)])
ng = set([(i,j) for i,j in zip([-2,-2,2,2],[-2,2,-2,2])])
while que:
y,x,c = que.popleft()
if cnt[y][x]<c:
continue
for i,j in ((1,0),(0,1),(-1,0),(0,-1)):
ny,nx = y+i, x+j
if 0<=ny<h and 0<=nx<w:
if g[ny][nx]!='#':
if c<cnt[ny][nx]:
cnt[ny][nx] = c
que.appendleft((ny,nx,c))
for i in range(-2, 3):
for j in range(-2, 3):
if (i,j) not in ng:
ny,nx = y+i,x+j
if 0<=ny<h and 0<=nx<w:
if c+1<cnt[ny][nx]:
cnt[ny][nx] = c+1
que.append((ny,nx,c+1))
print(cnt[-1][-1])
if __name__ == '__main__':
main()
考える移動は以下の2通り
- 道を伝う場合
- 左右上下のマスへの移動
- 移動にかかるコストは0
- パンチを行う場合
- 四隅を除いた上下左右へ2マスの範囲内へ移動可能となる
- 移動にかかるコストは1
道を伝う場合の方がコストは小さいので、appendleftによる枝刈りを行う
参考記事
Author And Source
この問題について( AtCoder Beginner Contest 213), 我々は、より多くの情報をここで見つけました https://zenn.dev/ohnuma/articles/00566d8c014022著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Collection and Share based on the CC protocol