読者です 読者をやめる 読者になる 読者になる

Codeforces Round #405 (rated, Div.2, based on VK Cup 2017 Round 1) 参加記

はい。 ox— (0/0) 1170(-23) http://codeforces.com/contest/791
Aのみ1完。Bは5回くらい提出したけどダメ。Bは多少は難度があったようでAC人数も多くなく1完でも軽症だった。

A. Bear and Big Brother

ざっくりと大意

・1ターン毎にaは3倍になり、bは2倍になる。aがbより大きくなるのはいつか?

Python3

a,b=map(int,input().split())
ans=chk=0
while a<=b:
    a*=3
    b*=2
    ans+=1
print(ans)

1 <= a,b <= 10 のようなのでシミュしてもループ抜けミスさえしなければ問題なさそう。

B. Bear and Friendship Condition

ざっくりと大意

・n個の頂点があってm本の辺の情報が与えられる。
・最終形が単独の頂点か、全ての頂点同士が辺で結ばれたグループになっていればYES、そうでなければNO??

Python2

n,m=map(int,raw_input().split())

e=[0]*n
t=[1]*n

r=[0]*n
p=[int(i) for i in range(n)]


def find(a):
    if a==p[a]:
        return a

#新しい親になる頂点を決めて辺や頂点の数をまとめる
    tmp=find(p[a])
    t[tmp]=t[tmp]+t[a]
    t[a]=0
    e[tmp]=e[tmp]+e[a]
    e[a]=0

    p[a]=tmp
    return p[a]

def unite(a,b):
    a,b=find(a),find(b)
    if a==b:
        return

    if r[a]<r[b]:
        p[a]=b
    else:
        p[b]=a
        if r[a]==r[b]:
            r[a]=r[a]+1
    k=p[a]
    if k!=a:
        t[k]=t[k]+t[a]
        t[a]=0
        e[k]=e[k]+e[a]
        e[a]=0
    if k!=b:
        t[k]=t[k]+t[b]
        t[b]=0
        e[k]=e[k]+e[b]
        e[b]=0


for i in range(m):
    a,b=map(int,raw_input().split())
    a-=1
    b-=1
    e[a]=e[a]+1
    unite(a,b)

p=set(p)
ans=1
for i in p:
    if t[i]>1:
        k=t[i]
        if e[i]!=k*(k-1)//2:
            ans=0
            break

print(['NO','YES'][ans])

もっと短いコードでいけるはず、というか実際にもっと短く書いてる人が多い。書いた内容としてはコンテスト中と同じ方針でUnionFindで書いたことあるテンプレ利用してグループ結合して、それとは別に辺の数も数えておく。全ての辺の受取が終わった後に各グループの辺が k * (k-1) / 2 本であるか、全ての頂点同士が結ばれているかを確認してYES,NOを出力した。 Editionalでもグループ内の頂点に対して必要な辺の数を前述の式で確認するらしいのでそれはそれでよいのかな。結合とかグループ管理、辺の本数メモとかをもうちょいっと楽にするのかな。まだもっと掘り下げる必要ありそう。

C. Bear and Different Names

ざっくりと大意

・1からnまで番号を付けられた兵士が並んでいる。k人の連続した番号でつくるグループで同じ名前があってはならない。
・サンプル1は1,2番目のグループはBobが2人いるのでNO、3,4,5番目のグループは同じ名前がいないのでYES、6番目のグループはAdamが2人いるのでNOという感じ?

先のグループのYES,NO次第で同じ名前の人の配置の仕方を変えたりしそうな??小さいパターンで法則性とか確認してからであとで。