🔥

AtCoder Beginner Contest 224

2022/04/06に公開約2,600字

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になるので注意です。

Discussion

ログインするとコメントできます