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
• パンチを行う場合
  • 四隅を除いた上下左右へ２マスの範囲内へ移動可能となる
  • 移動にかかるコストは1

道を伝う場合の方がコストは小さいので、appendleftによる枝刈りを行う
参考記事