AtCoder Beginner Contest 213

31196 단어 경업자tech

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()
정렬 후 두 번째 득점

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를 이용하여 유성 여행을 한다.
컴백이니까 싸이즈.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
  • 전도하면 원가가 적기 때문에 appeendleft로 편집합니다
    참고 문장

    좋은 웹페이지 즐겨찾기