AtCoder Beginner Contest 126

参加記 atcoder

はい。
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を使えばいい、と気づく人は頭良すぎだと思います。辛いですね。