AtCoder Beginner Contest 224

A - Tires


def main():
  s = input()
  print('er' if s[::-1][:2]=='re' else 'ist')

if __name__ == '__main__':
  main()
입력 문자열의 어미를 보고 판정하면 된다.
문자열의 길이를 고려하는 것은 매우 번거롭기 때문에 문자열이 반전된 후에 처음의 문자로 구분되었다.

B - Mongeness


def main():
  h,w = map(int, input().split())
  a = [list(map(int, input().split())) for _ in range(h)]

  flg = True
  for i1 in range(h-1):
    for i2 in range(i1+1, h):
      for j1 in range(w-1):
        for j2 in range(j1+1, w):
          if a[i1][j1]+a[i2][j2] > a[i2][j1]+a[i1][j2]:
            flg = False
  print("Yes" if flg else "No")

if __name__ == '__main__':
  main()
종횡 격자 크기가 50 정도이기 때문에 전체 탐색도 늦지 않다.

C - Triangle?


def func(xs, ys):
  return abs((xs[0]-xs[2])*(ys[1]-ys[2]) - (xs[1]-xs[2])*(ys[0]-ys[2]))/2

def main():
  n = int(input())
  lst = [list(map(int, input().split())) for _ in range(n)]
  ans = 0
  for i in range(n):
    for j in range(i+1, n):
      for k in range(j+1, n):
          ret = func([lst[i][0], lst[j][0], lst[k][0]], [lst[i][1], lst[j][1], lst[k][1]])
          if ret!=0:
            ans += 1
  print(ans)

if __name__ == '__main__':
  main()
정점 3점 좌표를 제시할 때의 삼각형 면적을 고려하면 된다.
여기 기사. 간단하고 이해하기 쉬우며 실제 계산된 면적 S가 0도 안 되는 상황을 모두 열거하면 된다.

D - 8 Puzzle on Graph


import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
inputs = sys.stdin.readline
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)

def to_str(lst):
  return ''.join(list(map(str, lst)))

def main():
  m = int(input())
  g = [[] for _ in range(10)]
  for _ in range(m):
    u,v = map(int, input().split())
    g[u].append(v)
    g[v].append(u)
  p = list(map(int, input().split()))
  pos = [0]+[9]*9
  for i,x in enumerate(p):
    pos[x] = i+1
  goal = [i for i in range(10)]
  used = set()
  que = deque([(pos, 0)])
  ans = inf
  while que:
    state, cnt = que.popleft()
    if state==goal:
      ans = min(ans, cnt)
    else:
      emp_idx = state.index(9)
      for nx in g[emp_idx]:
        nx_state = state[:]
        nx_state[emp_idx], nx_state[nx] = nx_state[nx], nx_state[emp_idx]
        txt = to_str(nx_state)
        if txt not in used:
          used.add(txt)
          que.append((nx_state, cnt+1))
  print(ans if ans!=inf else -1)

if __name__ == '__main__':
  main()
처음 보면 풀 수가 없어...!
순환 구조와 집합에 관심을 가질 줄 알았는데 계산량을 고려하면 BFS로 해결할 수 있다고 한다.참고 자료
디스크의 상태를 관리하는 BFS는 되지만 스풀보드 객체는 컬렉션에 추가할 수 없으므로 문자열로 변환하여 기존 상태를 판단합니다.
그나저나 복사 상태일 때,cope.deepcopy 를 사용하면 TLE 가 됩니다.

좋은 웹페이지 즐겨찾기