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になるので注意です。
Author And Source
この問題について(AtCoder Beginner Contest 224), 我々は、より多くの情報をここで見つけました https://zenn.dev/ohnuma/articles/5577ce667850c9著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Collection and Share based on the CC protocol