8VC Venture Cup 2017 - Elimination Round 参加記

はい。 oxo---- (0/0) 1306(-2)
http://codeforces.com/contest/755
最近は素数、素因数分解使うの流行ってるのかな？？ B問題はもう少し複数パターンのシミュと自作テストケース確認するべきだった。。

A. PolandBall and Hypothesis

ざっくりと大意

・入力の数がnで、n * m + 1が素数にならないようなmを探す。

Python3

def prime_t(t):
    i=2
    while i**2<=t:
        if t%i==0:
            return 0
        i+=1
    return 1

l=[]
for i in range(2,10000):
    if prime_t(i):
        l.append(i)

n=int(input())
for i in range(1,1001):
    if (n*i+1) not in l:
        print(i)
        exit()

入力の数も小さいし素数のリストを作っておいて1から総当りで素数になるか調べれば大丈夫だと思う。

B. PolandBall and Game

ざっくりと大意

・先手:PolandBallがn件の単語リストを使用、後手:EnemyBallがm件の単語リストを使用。
・リストの中から単語を選んで使用する。なお、相手側にも同じ単語があった場合には使えないように出来るために相手のリストを1語分減らすことが出来る。
・勝敗は先に使う単語が無くなった、リストが空になった方が負け。
・先手後手それぞれが最善手で行動した時にPolandBallが勝てるならYES、そうでなければNO。

Python3

n,m=[int(i) for i in input().split()]
p,e=set([]),set([])
for i in range(n):
    p.add(input())
for i in range(m):
    e.add(input())
tyo=p&e
n-=len(tyo)
m-=len(tyo)

if n+len(tyo)%2>m:
    print('YES')
else:
    print('NO')

リスト内に重複の単語がある時は重複を使うのが最善手。重複を使い切った後はリスト内に残ったものを使っていく流れになる。 重複が奇数件の場合は後手から減るので1件余裕あり？でn,mの残数がn>=mなら勝てる、重複が偶数件の場合は先手から減るので残数がn>mでないと勝てない。

C. PolandBall and Forest

ざっくりと大意

・n件の頂点があり、それぞれi番目の頂点と結合状態にあるグループ内の最も遠い頂点番号が\(p_i\)で与えられる。
・なお、最も遠い頂点が複数あった場合は最も若い番号が示される。

Python3

import heapq
n=int(input())
l=[int(i) for i in input().split()]
syu={}
ich=[]
d={i for i in range(1,n+1)}
for a,i in enumerate(l):
    if i in syu:
        syu[i]+=1
    else:
        syu[i]=1
        heapq.heappush(ich,i)
while len(ich):
    tmp=heapq.heappop(ich)
    if tmp<l[tmp-1]:
        syu[tmp]+=syu[l[tmp-1]]
        syu[l[tmp-1]]=0
ans=0
for i in syu:
    if syu[i]>0:
        ans+=1
print(ans)

サンプル1を見て同じグループになるかをi番目を見ると、xがあるのでiとxで若い番号の方をグループ内の親になる頂点ということにして〜〜とかやったが、pにある頂点の種類と2の商でも出来るらしいような？？