GCJ 2017 (Round1A) - 日々ｄｒｄｒする人のメモ

Google Code Jam 2017のRound1A参加
Dashboard - Round 1A 2017 - Google Code Jam

1000位以内で通過。結果は65ptsで、ぎりぎり1000位切れたのでRound2に進める。

以下、自分の解法

A. Alphabet Cake

問題

R*Cの長方形🎂が与えられて、幾つかのcellに子供達のイニシャルであるアルファベットが一つずつ書かれている。
🎂を各子供に対して、自身のイニシャルを一つ含むように長方形に分割せよ。

> 入力の🎂
A?D
?B?
???
??C
> 分割の一例
AAD
BBB
BBB
CCC

制約

Small: ${1 \le R, C \le 12, R \times C \le 12}$ ,
Large: ${1 \le R, C \le 25}$

解法

貪欲に分割した。
まずは、行単位で左から見ていき、割り当てが終わってないアルファベットを見つけ、blankでないcellが見つかるまで左右にアルファベットを割り当てていく。この時、行全体がblankなcellは全て'?'である。
次に、列単位で上から見ていき、割り当てが終わっている行を見つけ、割り当てが終わっている行が見つかるまで上下に行の内容をコピーして割り当てていく。
計算量は ${O(RC)}$ になるため、Largeまでいける。

for _ in xrange(input()):
    print "Case #%d:" % (_+1)
    r, c = map(int, raw_input().split())
    Cake = [list(raw_input()) for i in xrange(r)]
    used = set()
    for i in xrange(r):
        for j in xrange(c):
            ch = Cake[i][j]
            if ch != '?' and ch not in used:
                used.add(ch)
                dx = 1
                while j+dx < c and Cake[i][j+dx] == '?':
                    Cake[i][j+dx] = ch
                    dx += 1
                dx = -1
                while j+dx > -1 and Cake[i][j+dx] == '?':
                    Cake[i][j+dx] = ch
                    dx -= 1
    for i in xrange(r):
        if Cake[i][0] != '?':
            dy = 1
            while i+dy < r and Cake[i+dy][0] == '?':
                Cake[i+dy] = Cake[i]
                dy += 1
            dy = -1
            while i+dy > -1 and Cake[i+dy][0] == '?':
                Cake[i+dy] = Cake[i]
                dy -= 1
    print '\n'.join("".join(line) for line in Cake)

B. Ratatouille

問題

ratatouilleのレシピがあって、 ${N}$ 個の材料が必要である。i番目の材料は ${R_i}$ gで一つ作れる。
また、各材料のpackageが ${P}$ 個あって、i番目の材料のj個目のpackageは ${Q_{ij}}$ g含まれている。

今回は(数人分作れる)ratatouille kitを作成するが、そのkitに含まれる材料の量は、必要量の90%~110%を含む必要がある。
(例えば、M人分用のkitを作る場合、各種類の材料について ${0.9R_iM \le Q_{ik_i} \le 1.1R_iM}$ を満たすpackageを選択する必要がある。同じpackageは複数のkitには使えない。)

与えられたpackageから最大何個のkitが作れるかを出力せよ。

制約

${1 \le R_i \le 10^6, 1 \le Q_{ij} \le 10^6}$
Small: ${1 \le N \le 2, 1 \le P \le 8}$
Large: ${1 \le N \le 50, 1 \le P \le 50, N \times P \le 1000}$

解法

i番目の材料について、 ${Q_{ij}}$ は
${ceil(\frac{Q_{ij}}{1.1R_i})}$ 人分から ${floor(\frac{Q_{ij}}{0.9R_i})}$ 人分作れることが分かる。N種類の材料のあるpackageの組合せについて、この人数区間でN種類全て重なる区間が存在した時、そのpackageでその人数分のkitが作れることになる。
この事実を利用し、N種類の材料について、小さいpackageから区間が重なるかチェックし、作れるkitを見つけるようにした。kitが作れる場合はN種類全ての材料について次のpackageを見る、作れない場合はpackageの区間のmaxが一番小さい材料について次のpackageを見るようにした。
計算量は ${O(N^2P)}$ になるため、Largeまでいける。

これを単純に書いたら、区間が小数点誤差で見事に死んだので正しい区間を計算できるような処理を入れた。

誤差ケース
2 1
8 3
4400
1350
(=> '1'が正しいが小数点誤差により'0'になってしまった)

import math
for _ in xrange(input()):
    print  "Case #%d:" % (_+1),
    n, p = map(int, raw_input().split())
    R = map(int, raw_input().split())
    Q = [sorted(map(int, raw_input().split())) for i in xrange(n)]
    ids = [0]*n
    kmin = [None]*n
    kmax = [None]*n
    ans = 0
    def calc(i):
        j = ids[i]
        if j < p:
            kmin[i] = int(math.ceil(Q[i][j]/(1.1*R[i])))
            kmax[i] = int(math.floor(Q[i][j]/(0.9*R[i])))
            while Q[i][j] <= (kmin[i]-1)*1.1*R[i]:
                kmin[i] -= 1
            while (kmax[i]+1)*0.9*R[i] <= Q[i][j]:
                kmax[i] += 1
    for i in xrange(n):
        calc(i)
    while max(ids) < p:
        if max(kmin) <= min(kmax):
            ans += 1
            for i in xrange(n):
                ids[i] += 1
                calc(i)
        else:
            i = kmax.index(min(kmax))
            ids[i] += 1
            calc(i)
    print ans

C. Play the Dragon

問題

ドラゴン(体力 ${H_d}$ , 攻撃力 ${A_d}$ )とナイト(体力 ${H_k}$ , 攻撃力 ${A_k}$ )が戦っている。
ドラゴンであるあなたは次のことができる

Attack: 攻撃力分だけ相手の体力を削る
Buff: 自分の攻撃力を ${B}$ 上げる
Cure: 自分の体力を ${H_d}$ に回復
Debuff: 相手の攻撃力を ${D}$ 下げる

相手であるナイトはAttackのみを行う。

自分の体力が0にならないように相手の体力を0にする時、最速何ターンで達成できるかを出力せよ。
不可能ならば"IMPOSSIBLE"を出力せよ。

制約

Small: ${1 \le H_d, A_d, H_k, A_k, B, D \le 100}$
Large: ${1 \le H_d, A_d, H_k, A_k, B, D \le 10^9}$

解法

Smallが解きたかった。
戦略としてはDebuff → Buff → Attack、体力0になりそうになったらCureすることには気付く。
とりあえず、DFS書いたらバグって死。つらい。

コンテスト終わって少し直したら通った...。計算量は ${O(A_dH_kA_k)}$ になる。ちょっと工夫すれば ${O(A_dA_k)}$ にはなる。

for _ in xrange(input()):
    print "Case #%d:" % (_+1),
    Hd, Ad, Hk, Ak, B, D = map(int, raw_input().split())

    def debuff():
        res = buff(Hd, Ak)
        if D > 0:
            hp = Hd; ak = Ak
            turn = 0
            s = set()
            while ak > 0:
                if (hp, ak) in s:
                    break
                s.add((hp, ak))
                turn += 1
                if hp > ak - D:
                    ak -= D
                    hp -= ak
                    res = min(res, buff(hp, ak) + turn)
                else:
                    hp = Hd - ak
                    if hp <= 0:
                        return 10**18
        return res

    def buff(hp, ak):
        res = attack(hp, ak, Ad)
        if B > 0:
            ad = Ad
            turn = 0
            s = set()
            while ad < Hk:
                if (hp, ad) in s:
                    break
                s.add((hp, ad))
                turn += 1
                if hp > ak:
                    ad += B
                    hp -= ak
                    res = min(res, attack(hp, ak, ad) + turn)
                else:
                    hp = Hd - ak
        return res
    def attack(hp, ak, ad):
        hk = Hk
        turn = 0
        s = set()
        while hk > 0:
            if (hp, hk) in s:
                return 10**18
            s.add((hp, hk))
            turn += 1
            if hp > ak or hk - ad <= 0:
                hk -= ad
                hp -= ak
            else:
                hp = Hd - ak
        return turn

    res = debuff()
    if res >= 10**18:
        print "IMPOSSIBLE"
    else:
        print res