8VC Venture Cup 2017 - Elimination Round - 君はまるで砂漠に咲く、一輪の花。

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

def prime_list(tt):
    p_list=[]
    for i in range(2,tt+1):
        if prime_t(i):
            p_list.append(i)
    return p_list


chk=prime_list(10001)
n=int(input())
for i in range(1,1000):
    if n*i+1 not in chk:
        print(i)
        break

素数の一覧を作っておいてn * 1、 n * 2…していって素数ではなかったら解なので出力して終了。

B. PolandBall and Game

ざっくりと大意

・自分の手持ちがn個と相手の手持ちがm個でゲームをする。
・n, m間で共通の要素は先に使われると使えなくなる。先に手が出せなくなった方の負になる。
・サンプル2は、自分の番で"kremowka"を使って相手の"kremowka"がなくなる、相手は"wiedenska"を使う。自分の番で"wadowicka"を使う。相手にはもう手がないので自分の勝ちになる。

Python3

n,m=map(int,input().split())
a=set([input() for i in range(n)])
b=set([input() for i in range(m)])
chk=a&b
a-=chk
b-=chk
for i in range(n+m+1):
    if len(chk):
        chk.pop()
    elif i%2==0 and len(a):
        a.pop()
    elif i%2 and len(b):
        b.pop()
    else:
        print('YES' if i%2 else 'NO')
        break

上のはゲームをシミュレーションと同等で。重複の要素がある時は重複から使うのが互いに最善手。重複がなくなれば自分の手持ちを使う。出す手がなかったら偶数ターンか奇数ターンで勝敗判定する。立式して1行で判定しようとすると print('YES' if (len(a)>len(b)-len(chk)%2) else 'NO') となる。共通要素が奇数個ならそれ以外のは相手と同数以上で自分の勝ち、偶数個なら自分のが1個以上多い場合に勝ち。

C. PolandBall and Forest

ざっくりと大意

・k個の頂点とk-1の辺がある。それぞれは1からnまでのユニークなIDを持っている。全体でいくつのグループがあるか？
・\(p_1\)から\(p_n\)にはi番目の頂点からみて最も遠い頂点のidが書かれている、同じ遠さのものが複数あったらその中でもっとも小さな数が書かれている。

Python3

input()
l=[int(i) for i in input().split()]
ans=0
w=set([])
for a,i in enumerate(l):
    if a+1==i:
        ans+=1
    else:
        w.add(i)
print(ans+len(w)//2)

なんでこんな変な形式にしてるのかよくわからん。〜, this problem is interactive. However〜とか書いてるけど、入出力の情報が対話式って感じじゃないし。提出結果で見られる入力内容は1行目に頂点数と辺の数があって、以降に辺の情報になっている。問題文のほうにもInput、Hackingで変なことを書いているが実際に与えられているのはサンプルと同様の形式の一行目に頂点数と2行目にそれぞれの頂点のが属するグループの中で最も遠く若い番号の頂点が、である。
サンプルと同じ形式の頂点数がと2行目に数列pならば、 \(p_i\)の値と番目が等しいものはどことも繋がっていない単独の頂点。どこかと繋がっている場合は同じグループ内で最も遠く若い頂点の番号は2種類しか存在しないらしいのでset型にいれて要素数を2で割るとグループの数になる。