AtCoder Beginner Contest 126
はい。
https://atcoder.jp/contests/abc126
oooo-- unratedでした。
A - Changing a Character
PyPy3
n,k=map(int,input().split()) s=list(input()) s[k-1]=s[k-1].lower() print("".join(s))
最近は使ってなくてlower()をド忘れしててググった。ググりながらordしてchrも検討したけどもlower()にしました。
B - YYMM or MMYY
PyPy3
s=int(input()) a=s//100 b=s%100 if 0<a<13 and 0<b<13: print("AMBIGUOUS") elif a==b==0 or (a>12 and b>12) or (a==0 and b>12) or (a>12 and b==0): print("NA") elif a>12 and b<13 or (a==0 and 0<b<13): print("YYMM") elif b>12 and a<13 or (b==0 and 0<a<13): print("MMYY")
サンプルを見ながら場合分けを頑張りましょう。。。
C - AB Substrings
PyPy3
def sol(): n,k=map(int,input().split()) ans=0 for i in range(1,n+1): f=0 while 1: if i>=k: break i*=2 f+=1 ans+=(1/n)*(1/(2**f)) print(ans) if __name__=="__main__": sol()
確率とか面倒そうで嫌だなぁ、でD問題より後回しにしたけど問題文とサンプルをよくみたら大して面倒でもなかった。サンプル1の式のとおりに書けばなんとかなります。多分。
D - DivRem Number
PyPy3
from collections import deque def sol(): n=int(input()) d=[-1]*n l=deque([]) for i in range(n-1): u,v,w=map(int,input().split()) u,v=min(u,v),max(u,v) l.append((u-1,v-1,w)) f=0 while len(l): x=l.popleft() if f: if x[2]%2 and d[x[0]]==0: d[x[1]]=1 elif x[2]%2 and d[x[0]]==1: d[x[1]]=0 elif x[2]%2==0 and d[x[0]]==1: d[x[1]]=1 elif x[2]%2==0 and d[x[0]]==0: d[x[1]]=0 elif x[2]%2 and d[x[1]]==0: d[x[0]]=1 elif x[2]%2 and d[x[1]]==1: d[x[0]]=0 elif x[2]%2==0 and d[x[1]]==1: d[x[0]]=1 elif x[2]%2==0 and d[x[1]]==0: d[x[0]]=0 else: l.append(x) else: f=1 if x[2]%2: d[x[0]]=0 d[x[1]]=1 else: d[x[0]]=0 d[x[1]]=0 for i in d: print(i) if __name__=="__main__": sol()
問題文を読んだ。何処かの任意の頂点の塗り始めは白黒どちらでもいいだろうなと思いました。「この問題の制約下では、そのような塗り分け方が必ず1つは存在することが証明できます。」ということなのでどちらで塗り始めても必ず1つに対して反転した塗り方があるはずなので塗り始めはどちらでもいいだろうなと思いました。後は塗り始めに対して距離の偶奇で塗ったり、どちらかの頂点が塗られていなかったら後回しにしたりしてを繰り返すようにしました。後はお試しで if __name__
で提出してACしました。
E - 1 or 2
PyPy3
class UnionFind: def __init__(self, size): self.rank=[0]*size self.par =[int(i) for i in range(size)] self.grp =size def find(self, x): if x==self.par[x]: return x self.par[x]=self.find(self.par[x]) return self.par[x] def same(self, x, y): return self.find(x)==self.find(y) def unite(self, x, y): x,y=self.find(x),self.find(y) if x==y: return self.grp-=1 if self.rank[x]<self.rank[y]: self.par[x]=y else: self.par[y]=x if self.rank[x]==self.rank[y]: self.rank[x]+=1 def group_num(self): return self.grp n,m=map(int, input().split()) uf=UnionFind(n) for i in range(m): x,y,z=map(int, input().split()) uf.unite(x-1,y-1) print(uf.grp)
先にUnionFindを使うというヒントを見かけてしまってAC。残念ですね。。。
問題文をもっとよく読むべきだったかなと。
手元でもっと色々試すべきだったかなと。
与えられる入力には矛盾がないことが保証されるらしいです。
なぜにグループ数で解になっているかは2枚のカード、3枚のカード・・・は全てのカードのX Y Zの情報があっても1 or 2を特定することは出来ません。出来ませんがX Y Zで情報を得た関係のあるカードは、ある1枚が特定できれば全て定まります。多分。サンプル2が凄いヒントです。
1 2 1 で1枚目と2枚目のどちらかだけが1で、もう一方は必ず2ということがわかります。
2 3 2 で1枚目と2枚目が共に1、または2であることがわかります。
1 3 3 で1枚目と3枚目のどちらかだけが1で、もう一方は必ず2ということがわかります。
これで1-3枚目の全ての情報を得ましたがこれだけではどのカードも特定出来ません。1 2 2と2 1 1のどちらもあり得ます。あり得ますが1枚だけわかれば全てを特定出来るはずです。多分。証明はここにはありません。ここらへんからX Y Zで情報の与えられたカード同士がグループになる。グループに対して1回の魔法でグループ内は全て特定出来るようになる。
でUnionFindを使えばいい、と気づく人は頭良すぎだと思います。辛いですね。