AtCoder Beginner Contest 067/AtCoder Regular Contest 078
はい。
https://atcoder.jp/contests/abc067
A - Sharing Cookies
Python3
a,b=map(int,input().split()) print("Possible" if (a%3==0 or b%3==0 or (a+b)%3==0) else "Impossible")
ほぼ問題文の通りにA,B,A+Bのどれかが3で割りきれるかを確認して判定。
B - Snake Toy
Python3
n,k=map(int,input().split()) l=[int(i) for i in input().split()] l.sort() print(sum(l[-k:]))
ソートして大きい方からk個使えば長さの最大値になるはず。
C - Splitting Pile
Python3
n=int(input()) a=[int(i) for i in input().split()] i=a[0] j=sum(a)-i ans=abs(i-j) x=1 while (x+1)!=n: i+=a[x] j-=a[x] ans=min(ans,abs(i-j)) x+=1 print(ans)
先頭から1つずつずらして見ていくしかないと思う、多分。
D - Fennec VS. Snuke
PyPy3
from collections import deque n=int(input()) d={} for i in range(n-1): a,b=map(int,input().split()) if a in d: d[a].append(b) else: d[a]=[b] if b in d: d[b].append(a) else: d[b]=[a] f,s=set([1]),set([n]) e=deque([0,1]) u=deque([0,n]) x=0 while 1: if len(e)==len(u)==1: break if len(e)>0: while e[-1]!=0: tmp=e.pop() for i in d[tmp]: if i not in f and i not in s: f.add(i) e.appendleft(i) e.rotate() if len(u)>0: while u[-1]!=0: tmp=u.pop() for i in d[tmp]: if i not in f and i not in s: s.add(i) u.appendleft(i) u.rotate() print(["Fennec","Snuke"][len(f)<=len(s)])
先手と後手の中間にある頂点の塗り方の最善手の調べ方に結構悩みました。中間を塗り進めるのに分岐する経路があった場合にどの辺を選ぶのが最善手になるのかをどうやって調べるかを悩みました。悩みましたが結果としては特に気にする必要はありませんでした。
頂点N個で辺がN-1なので1とNは一本道で繋がっているはずです。1からとNからのそれぞれを1手ずつ○手目で塗り可能な頂点を幅優先で選択し続けていきます。先に塗られた頂点に上塗りはしません。サンプル2のように1とNが隣接している場合もありえます。最後まで選択し続けた○手目で塗り可能な頂点の合計が最善手で塗り可能な頂点数です、多分。そしてココに証明はありません。