Google Code Jam 2018: Qualification Round

Google Code Jamに今年もチャレンジ。

(昨年の: Google Code Jam 2017: Qualification Round - すぎゃーんメモ)

今年もRubyで、と思って最初の問題を解いてコード提出してみたのだけど、Runtime Errorになって上手くいかなくて、なんで？？と思ってPython3に変更して(結局Runtime Errorは単純なバグだったんだけど) そのまま他の問題もPython3で提出した。

Saving The Universe Again

C (charge) と S (shoot) からなる文字列が与えられ、倍々になって蓄積されるダメージを一定量まで減らすための最低操作回数を求める。

文字列を1つずつ読んでいけばダメージ総量はすぐに求められる。あとはこれをどのように減らしていけるか。 効率的に減らすためには最大ダメージのもの つまり最後方にあるSを直前のCと交換することで つまり1回の操作は「ダメージ最大のものを半分に減らすこと」と考えられる。 初期値のダメージ総量は1回だけ計算すればよくて、あとはshootによるダメージと回数の辞書を作って 最大ダメージのものから選択してその回数を減らし 半分の値の辞書エントリの回数の方に加える。減少させた総量 > ダメージ初期値 - 防御力になるまでそれを繰り返せばよさそう。 足し算引き算を繰り返しても良かったけど、掛け算的に一気に処理もできるな、と思ってそうしてみた

t = int(input())
for i in range(1, t + 1):
    d, p = input().split(' ')
    d = int(d)
    dam = {}
    s = 1
    for c in list(p):
        if c == 'C':
            s *= 2
        if c == 'S':
            dam[s] = dam.get(s, 0) + 1
    s = sum([k * v for k, v in dam.items()])
    a = 0
    while s > d:
        m = max(dam.keys())
        if m == 1:
            a = 'IMPOSSIBLE'
            break
        r = m / 2 * dam[m]
        if s - r > d:
            s -= r
            a += dam[m]
            dam[int(m / 2)] = dam.get(int(m / 2), 0) + dam[m]
            del(dam[m])
        else:
            a += int((s - d) / (m / 2))
            if (s - d) % (m / 2) != 0:
                a += 1
            break
    print('Case #{}: {}'.format(i, a))

Trouble Sort

数値の列が与えられたときに「順番に連続の3つの数字並びを見て 左端より右端の数値の方が大きくなるようswapする」という操作を繰り返すsortingを行ったときに、正しくsortされない箇所を求める。

実際にこれを実行するとそれなりに実行時間がかかるはずなのでシミュレーションして求める、のはダメそう。 とはいえどうすれば良いか分からなかったので最初は実際にそれを実装してランダムな初期値を与えて実行結果を観察してみた。 先頭に来るべき最小値が0番目じゃなくて1番目に来ることがある… 2番目に小さな値が先頭に来たり… → はっ これは初期状態の位置が偶数番目か奇数番目かによるな → そういえばn番目の要素はn+2番目の要素としか交換しないのか →つまり奇数番目の要素による数値列と偶数番目の要素による数値列が別々にsortされる、と考えれば良いのか、とようやく気付いた。

あとは普通に分けてsortしたものを先頭から比較して見ていって 昇順でなくなるところを検出する。

t = int(input())
for i in range(1, t + 1):
    n = int(input())
    v = [int(e) for e in input().split(' ', n)]
    a = 'OK'
    e, o = [], []
    for j, val in enumerate(v):
        if j % 2 == 0:
            e.append(val)
        else:
            o.append(val)
    e.sort()
    o.sort()
    for j in range(len(o)):
        if e[j] > o[j]:
            a = j * 2
            break
        if j < len(e) - 1 and o[j] > e[j + 1]:
            a = j * 2 + 1
            break
    print('Case #{}: {}'.format(i, a))

Test set 2 では 3 <= N <= 10 ** 5 とのことで10万要素あると普通のsortも結構時間かかってダメかも…？と思ったけど それ以上の方法が思い付かなかったのでこのまま提出。

Go, Gopher!

なんか問題が複雑そうで読むのもつらかったので捨て…

Cubic UFO

立方体による影の面積が指定された値になるよう回転させたときの各面の座標を求めよ、というもの

すごい難しそう、とは思ったものの、Test set 1は 1.000000 ≤ A ≤ 1.414213という制約があったので、0°から45°までのz軸固定の回転のみで考えても良さそう。 Aの面積は cos(回転角 - 45°) * sqrt(2)で算出できるのは単純な計算で分かるので、それを解いて必要な回転角度を出して、それをもとに座標を出す。

import math

t = int(input())
for i in range(1, t + 1):
    a = float(input())
    r = 45.0 * math.pi / 180.0 - math.acos(a / math.sqrt(2))
    print('Case #{}:'.format(i))
    print('{:.8f} {:.8f} 0.0'.format(0.5 * math.cos(r), 0.5 * math.sin(r)))
    print('{:.8f} {:.8f} 0.0'.format(-0.5 * math.sin(r), 0.5 * math.cos(r)))
    print('0.0 0.0 0.5')

明らかにTest set 1のみのための解法でTest set 2には絶対通らないけど、これで提出

結果

"Saving The Universe Again", "Trouble Sort" は無事にどちらも正解だったようで、"Cubic UFO"のTest set 1の正解もあわせて合計49ptで通過した模様。

次のRoundはもう全然通過できる気がしないけど頑張ろう…