🔥

2022/04/06に公開

# 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()
``````

# 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()
``````

こちらの記事がわかりやすく、実際に求まる面積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
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:
que.append((nx_state, cnt+1))
print(ans if ans!=inf else -1)

if __name__ == '__main__':
main()
``````

ループ構造や集合に注目するのかと思っていましたが、計算量を考えるとBFSで解けるそうでした。参考

ちなみに状態をコピーする際に、cope.deepcopyを使うとTLEになるので注意です。

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