f:id:ejinote:20180408110839p:plain

ラボの助教+ラボ同期に誘われてGoogle Code Jam 2018の予選に参加しました。

まるまる1日使うコンテストは初めてだったので、どういうテンションで望めばいいか全く分かりませんでした。結果的に問題を見てから4時間くらい放置してAmazon Prime Video見てしまったので若干反省しています。

パスしたかコンテスト中に分かるVisible Caseとコンテストが終わってから分かるHidden Caseが存在するのは面白いですね。 4問すべてのVisible Caseが通れば予選突破が確定するシステムもなかなか良いと思いました。

一方でサーバーが激重だったりうちのネット回線がカスだったりしたせいでsubmit連打してたらWAがたくさん生えて辛かったです。

振り返り

Saving The Universe Again

前にShootを固めるほどダメージが下がること、後ろのShootの方がダメージが大きいこと、を考えて、文字列を後ろから舐めてCを後ろに追いやれば良い。

初Google Code Jamだったこともあり、python3.6以降でしか使えないfstringを使って1回WA+隣り合った2つしか交換できないのを見落としていて1WA。

def calc(P):
    ans = 0
    damage = 1
    for c in P:
        if c=='S':
            ans += damage
        elif c=='C':
            damage *= 2
    return ans

def swap(P):
    for i in reversed(range(len(P))):
        if P[i-1:i+1] == 'CS':
            return P[:i-1] + 'SC' + P[i+1:]
    return None
    
def main():
    T = int(input())
    for i in range(1, T+1):
        D, P = input().split()
        D = int(D)
        cnt = 0

        while calc(P)>D:
            cnt += 1
            P = swap(P)
            if P is None:
                cnt = 'IMPOSSIBLE'
                break
        
        print('Case #{}: {}'.format(i, cnt))

if __name__=='__main__':
    main()

Trouble Sort

擬似コードが問題文中に書かれているので愚直に実装して、あとはsort使ったやつと比較しておしまい…… だと勘違いして計算量の見積りをしなかったためHidden CaseでTLE。

追記：偶数番目と奇数番目のリストをソートして、前から順に比較するだけで通る。

Go Gopher

インタラクティブな形式の問題。

長方形の形を $3 \times x$ マスに固定して、周囲が塗られたマスが少ない順にクエリを投げていけば通る。

テスト用にtesting_tool.pyが配られているので、そのテストケースを上限いっぱいにして通ることを確認。

import sys
import math

def main():
    t = int(input())
    for i in range(t):
        a = int(input())
        w = math.ceil(a/3)
        area = {i:0 for i in range(2,w)}
        checked = set()
        while True:
            # query
            x = min(area, key=lambda x: area[x])
            print(x, 2, flush=True)

            # update
            x, y = map(int, input().split())
            if x==0 and y==0:
                break
            if x==-1 and y==-1:
                sys.exit()
            if (x, y) not in checked:
                checked.add((x, y))
                for j in [-1, 0, 1]:
                    if not 2<=x+j<=w-1:
                        continue
                    area[x+j] += 1
            
if __name__=='__main__':
    main()

Cubic UFO

立方体を射影した面積に対応する回転角を求める問題。 scipyとかの非標準ライブラリが使えるか分からなかったのでニュートン法で解くことに。numpyとかscipyとか使えるんですかね？？

$A\leq\sqrt{2}$ のときは $x$ 軸まわりだけ回せばOK。陰は縦 $1$ 、横 $\cos{\theta}$ の長方形になる。面積最大になるのは $\theta=\pi/4$ のとき。

$A>\sqrt{2}$ のときは $x$ 軸まわりに $\pi/4$ 回した状態から $z$ 軸回りに回転させれば良い。形としては六角形。面積最大になるのは $\arcsin(\frac{1}{\sqrt{3}})$ 回転させた時。 (投影図かなにかを書きながら六角形の面積を考えると) 最終的には $\alpha = \arccos(\frac{1}{\sqrt{3}})$ として、 $\sqrt{2}\cos{\theta}+\frac{\sqrt{2}}{2}\left(\sqrt{3}\cos{(\alpha-\theta)}-\cos{\theta}\right)=A$ を満たす $\theta$ を探す問題に帰着される。

でも、これ手元でテストするのが難しい(面倒くさい)と思う。Visible CaseとHidden Caseで全くロジックが違うってどうなんだ？うまい方法ある人は教えてください。

from math import *

def newton(f, g, x, eps=1e-8):
    while abs(f(x)) > eps:
        x -= f(x)/g(x)
    return x

def rotate(x, y, z, rx=0, rz=0):
    # rotate around x
    y, z = y*cos(rx)-z*sin(rx), y*sin(rx)+z*cos(rx)
    # rotate around z
    x, y = x*cos(rz)-y*sin(rz), x*sin(rz)+y*cos(rz)
    return (x, y, z)

T = int(input())
for i in range(1, T+1):
    A = float(input())
    x = 0.5
    d45 = pi/4
    print('Case #{}:'.format(i))
    if A <= sqrt(2):
        theta = newton(
            f=lambda theta: sqrt(2)*cos(d45-theta)-A,
            g=lambda theta: sqrt(2)*sin(d45-theta),
            x=0
        )
        # print(degrees(theta%(2*pi)))
        print(*rotate(0.5, 0, 0, theta))
        print(*rotate(0, 0.5, 0, theta))
        print(*rotate(0, 0, 0.5, theta))
    else:
        alpha = acos(1/sqrt(3))
        theta = newton(
            f=lambda theta: sqrt(2)/2*cos(theta)+sqrt(6)/2*cos(alpha-theta)-A,
            g=lambda theta: -sqrt(2)/2*sin(theta)+sqrt(6)/2*sin(alpha-theta),
            x=0
        )
        # print(degrees(theta%(2*pi)))
        print(*rotate(0.5, 0, 0, d45, theta))
        print(*rotate(0, 0.5, 0, d45, theta))
        print(*rotate(0, 0, 0.5, d45, theta))