Wunder Fund Round 2016 (Div.1 + Div.2 combined) - 君はまるで砂漠に咲く、一輪の花。

A. Slime Combining

ざっくりと大意

・始めは1のスライムが増えてnになる？？？よくわからないのでNoteみてエスパーを。

n=int(raw_input())
x=bin(n)[2:]
x=x[::-1]
for i in range(len(x)-1,-1,-1):
    if x[i]=='1':
        print i+1

2進数で1が立ってる桁が解になる。Noteからヒントを得るしかなかった。

B. Guess the Permutation

ざっくりと大意

・n * nの数列aがある。\(a{i_j}\)はmin(\(p\i), \(p_j\))で定まる。1からnで構成される数列pを出力する。

Python

n=int(raw_input())
for i in range(n):
    l=map(int,raw_input().split())
    if len(set(l))==n:
        l[l.index(0)]=n
        print ' '.join(map(str,l))
        exit()

サンプル見てたらなんとなく0からn-1が全て出ている行を使って、0をnに置換するだけでなんとかなるんじゃないか？？と思ってあまり検証せずに出したらACだった。ちょっと嬉しい。

C. Constellation

ざっくりと大意

・n個、1からnまでのナンバリングの星が夜空にある。
・3点を選んで正の面積(positive area)で三角形を構成して、その3点の中にほかの点が含まれないようなものを選ぶ。

Python2

IS=float('inf')

def euclid(x1,y1,x2,y2): return ((x1-x2)**2+(y1-y2)**2)

n=int(raw_input())
a,b=map(int,raw_input().split())
c,d=map(int,raw_input().split())
chk=[[a,b,1],[c,d,2],[]]
l=[[c,d,2]]
memo=euclid(a,b,c,d)
for i in range(n-2):
    x,y=map(int,raw_input().split())
    l.append([x,y,i+3])
    t=euclid(a,b,x,y)
    if t<memo:
        chk[1]=[x,y,i+3]
        memo=t
t=IS
for i in l:
    a=chk[1][0]-chk[0][0]
    b=chk[1][1]-chk[0][1]
    c=i[0]-chk[0][0]
    d=i[1]-chk[0][1]
    tmp=abs(a*d-b*c)
    if tmp>0 and tmp<t:
        chk[2]=i
        t=tmp
print chk[0][2],chk[1][2],chk[2][2]

答えは複数パターンありうるようになっている。1点目は最初の点で決め打ちする。最終回答用の1番目には入れるが、比較用の配列には入れない。2点目は最終回答用の2番目と比較用の配列に入れる。3点目以降は1点目との距離がより近ければ最終回答用のを更新する。距離にはかかわらず比較用にも入れる。全部の点を受け取った後には最終回答用の配列には1が1番目の点、2がそれに最も近い点、3は空となっているはず。比較用の配列には2番目以降の点の情報が全て入っているはず。最終回答用の1,2番目の点と、比較用の点を総当りで面積を比較して0より大きい最小の面積のものを3番目の点として更新し続けて全部調べ終わったらそれが回答になるらしい。
距離を比較するときは相対的に遠近を知りたいだけなので2乗の値のままのほうが良いと思う。平方根で距離を実数で求めても誤差で罠があるかもしれないし、計算時間も無駄だと思う。三角形の面積で最小のものを比べるときも2.0で割る必要は無いと思う。あと、3点を選んで一直線でさえなければ正の面積だと思う。