Codeforces Round #385 (Div.2) - 君はまるで砂漠に咲く、一輪の花。

A. Hongcow Learns the Cyclic Shift

ざっくりと大意

・末尾の文字を先頭に移動させるという操作を繰り返して何種類の文字列が作れるか。

Pypy3

s=input()
ans=1
chk=s
for i in range(len(s)):
    chk=chk[-1]+chk[:-1]
    if chk!=s:
        ans+=1
    else:
        break
print(ans)

文字列の長さが最大で50なので50パターンを全部set型にいれて要素数を見たり、1つずつカウントして初期の文字列sと同じになったら即時終了のどちらでも大丈夫だと思う。

B. Hongcow Solves A Puzzle

ざっくりと大意

・2つの同じパズルピースを見つけ四角形を作る。文字'X'はピースの一部を表し、文字'.'は空の部分である。
・ピースは4接続であることが保証される。また、'X'の中は空洞であってはならない。

Pypy3

n,m=[int(i) for i in input().split()]
flg=0
ans=1
chk=''
for i in range(n):
    tmp=input()
    if flg==0 and 'X' in tmp:
        chk=tmp
        tmp=tmp.rstrip('.').lstrip('.')
        if '.' in tmp:
            ans=0
            break
        else:
            flg=1
    elif flg==1 and 'X' in tmp:
        if chk!=tmp:
            ans=0
            break
    elif flg==1 and 'X' not in tmp:
        flg=2
    elif flg==2 and 'X' in tmp:
        ans=0
        break
print('YES' if ans else 'NO')

'X'が空洞のない四角形(1 * 1含む)になっていればいいらしい。あとは入力で、

input

3 3
XXX
...
XXX

みたいな'X'が途切れた形が無いことも保証されているらしい(ピースが4接続の形で保証されているから？)。

C. Hongcow Builds A Nation

ざっくりと大意

・全体ではn個のノード(都市)があり、その内のk個のノード(政府)は別の国であり辺(道路)で接続されることはない。
・k個の政府をお互いに接続させずに追加できる辺(道路)は最大で何本か？？
・サンプル1は4個の都市があり、政府は1,3の頂点。1,2には辺がある。最大の本数は1,4と2,4の2本。
・1,2間には既に辺があり、3は1の政府とは接続できないので1,2のどちらにも接続できない。4はどことも接続されていないくて、1,3のどちらにも接続可能であるが、辺が最大になるのは1の政府に接続した時。

Python2

import sys

sys.setrecursionlimit(100000)
def find(x):
# d[x]==x になるのは根になる頂点の時?
    if d[x]==x:
        return x

    d[x]=find(d[x])
    return d[x]

n,m,k=map(int,raw_input().split())
syuto=map(int,raw_input().split())
d={i:i for i in range(1,n+1)}

for i in range(m):
    u,v=[find(x) for x in map(int,raw_input().split())]
    d[u]=v

cnt=[]
for i in syuto:
    chk=0
    for j in range(1,n+1):
        if find(j)==find(i):
            chk+=1
    cnt.append(chk)

cnt.sort()
ans=0
for i in range(len(cnt)-1):
    ans+=cnt[i]*(cnt[i]-1)/2
    n-=cnt[i]
ans+=n*(n-1)/2
print ans-m

写経した。連想配列でそれぞれの頂点の接続されている親を管理する、多分？辺の入力受取だけでは親の情報が更新されていない場合があるのをfind(j)==find(i)で更新する、多分。辺の入力中に{1,2,3}と{4,5,6}があるところに更に3,4を繋ぐ辺を入力しても3,4以外の頂点の親の情報は更新されないため。更新しつつ政府がある集まりに幾つの頂点があるかを数えて配列に入れる。
配列をソートして、配列の長さ-1の分だけ(配列中の最大値の手前まで)forで回してx(x-1)/2で頂点数xの時に最大の辺の数をansに加算して、既に政府に接続されている頂点数はnから引く。
nはどこの政府にも接続されていない頂点数が残る(政府に接続されていない同士で接続されている場合を含む)残ったn個の頂点での最大の辺の数をansに加算して、最後に入力で与えられた辺の数mを引いたものが解になる、らしい。