2015 google codejam QR 문제 풀이

qualification round가 이렇게 어려울 줄이야..

괜히 저녁에 시작했다가 피봤다.

체력을 엄청 소비하고 겨우 통과했네.

A. Standing Ovation

첫 문제는 쉬웠다.

보통 이건 잘 푸는 것 같다. ide 세팅시간 합쳐서 20분 정도 걸렸던 듯.

import sys
import os
#import numpy as np
import itertools

sample = "sample"
small = "A-small-attempt0"
large = "A-large"
current = large

fin = open(current + ".in", "r")
fout = open(current + ".out", 'w')
f1out = open(current + "1.out", 'w')
f2out = open(current + "2.out", 'w')

T = int(fin.readline())

def solve(N, ss):
    f = 0
    c = 0
    for i, s in enumerate(ss):
        if c < i:
            f += i - c
            c += i - c

        c += s

    return f, c

for i in range(T):
    N, S = fin.readline().split()
    ss = []
    for j in range(int(N)+1):
        ss.append(int(S[j]))
    solution = solve(int(N), ss)
    answer = "Case #%d: %s\n" % (i+1, solution[0])
    print answer
    fout.write(answer)



fin.close()
fout.close()
f1out.close()
f2out.close()

B. Infinite House of Pancakes

처음에는 문제를 잘못 이해했다. 1분짜리 move를 할 때, 여러 접시에서 이동할 수 있는 줄 알았는데, 한 접시에서만 pancake를 이동하는 거였네.

여기서 완전 말렸다.

5시간을 소비해도 못 풀었다 T_T

시간이 많이 걸렸을 때 빨리 포기하고 다른 문제를 풀었어야 했는데, 괜히 고집을 부렸다. 쉽게 풀릴 것만 같아서..

내가 틀렸다는 생각은 안하고..

왠지 testcase에 9가 n번 들어간 testcase가 많았었는데,

난 9를 4, 5로 나누려고 했었지만, 3, 3, 3으로 나누는 것이 좋을 때가 있었다! 다음 날 깨달았다.

C. Dijkstra

quaternion 계산식을 구현하는 것에만 한참 걸렸다. 역시나 class로 만드는 것은 괜히 무리한 건가.

3시간은 걸렸던 듯.

1.5시간은 quaternion class에 소비했던 것 같다.

처음에는 multiplication을 빠르게 하려고 고생했는데, 그렇게 노력할 필요가 없었다.

어차피 최소 1번은 죽 다 읽어야 하고,

각 조합에 대해서 반복 계산할 필요가 없었네..

그리고, 중요한 것은 4번 곱셈마다 값이 반복되니까 반복에 대해서 계산할 필요가 없을 때도 있다는 것.

sample = "sample"
small = "C-small-attempt3"
large = "C-large"
current = large

fin = open(current + ".in", "r")
fout = open(current + ".out", 'w')
# f1out = open(current + "1.out", 'w')
# f2out = open(current + "2.out", 'w')

T = int(fin.readline())

q_order = {'i':-1, 'j':0, 'k':1}
q_next = {'i':'j', 'j':'k', 'k':'i'}

class Quaternion:

    def __init__(self, sign, v):
        self.sign = sign
        self.v = v

    def qorder(self):
        return q_order[self.v]
    def qnext(self):
        return Quaternion(self.sign, q_next[self.v])

    def __mul__(self, other):
        sign = not (self.sign ^ other.sign)

        if self.v == '1':
            return Quaternion(sign, other.v)
        if other.v == '1':
            return Quaternion(sign, self.v)
        if self.v == '0' or other.v == '0':
            return Quaternion(sign, '0')

        if self.v == other.v:
            return Quaternion( not (sign ^ False), '1')

        if self.qnext().v == other.v:
            return Quaternion(sign, other.qnext().v)
        else:
            return Quaternion( not (sign ^ False), self.qnext().v)

        print 'ERROR'

    def __neg__(self):
        return Quaternion(not (self.sign ^ False), self.v)

    def __eq__(self, other):
        # if other == 1:
        #     return self.sign == True and self.v == '1'
        # elif other == -1:
        #     return self.sign == False and self.v == '1'

        return self.sign == other.sign and self.v == other.v

    def __repr__(self):
        sign = '+' if self.sign else '-'
        return sign + self.v

def q(s):
    return Quaternion(True, s)

def mult(qs):
    r = q('1')
    for vq in qs:
        r = r * vq
    return r

def mult_table(table, vs, a, b, indices):
    key = str(a) + ',' + str(b)
    if table.has_key(key):
        return table[key]
    else:
        cs = [x for x in indices if a < x < b]
        if not cs:
            value = mult(vs[a:b])
        else:
            c = cs[len(cs)/2]
            value = mult_table(table, vs, a, c, indices) * mult_table(table, vs, c, b, indices)
            #print key, value, a, c, b
        table[key] = value
        return value

#print q('i') * q('j'), q('j') * q('k'), q('i') * q('j') * q('k')
def solve(L, X, ijk):
    fqs = []
    for i in ijk:
        if i == 'i' or i == 'j' or i == 'k':
            fqs.append(q(i))
    qs = []
    X = X % 16
    extend = min(X, 4)
    for i in range(extend):
        qs.extend(fqs)


    print qs
    lq = q('1')
    left_plus = []
    left_minus = []
    for i_l, l in enumerate(qs):
        # print lq, l
        lq = nx = lq * l
        if nx == q('i'):
           left_plus = [i_l+1, nx, l]
        if nx == -q('i'):
            left_minus = [i_l+1, nx, l]
        if left_plus and left_minus:
            break

    right_plus = []
    right_minus = []
    rq = q('1')
    for i_r, r in enumerate(reversed(qs)):
        rq = nx = r * rq
        if nx == q('k'):
            right_plus = [i_r+1, nx, r]
        elif nx == -q('k'):
            right_minus = [i_r+1, nx, r]
        if right_plus and right_minus:
            break

    if (not left_plus) and not left_minus:
        return "NO"
    if not right_plus and not right_minus:
        return "NO"

    dqs = []
    for idqs in range(X):#range(min(X, 8)):
        dqs.extend(fqs)

    lefts = []
    rights = []

    mc = {}
    mfqs = mult(fqs)
    indices = []
    if left_plus:
        indices.append(left_plus[0])
        lefts.append(left_plus)
    if left_minus:
        indices.append(left_minus[0])
        lefts.append(left_minus)
    if right_plus:
        indices.append(len(dqs) - right_plus[0])
        rights.append(right_plus)
    if right_minus:
        indices.append(len(dqs) - right_minus[0])
        rights.append(right_minus)
    for ie in range(8):
        index = ie * len(fqs)
        indices.append(index)
        mc[str(index) + ',' + str(index + len(fqs))] = mfqs
    sorted_indices = sorted(set(indices))

    # prev = -1
    # mc = mult_table(qs, sorted_indices)
    # for ii in sorted_indices:
    #     for ij in sorted_indices[]:
    #         if
    #     if prev > 0
    #         mc[[prev, index]] = mult(qs[prev:index+1])
    #     prev = index


    print mfqs, mc, sorted_indices
    for j_l in lefts:
        for j_r in rights:
            if j_l[0] + j_r[0] < len(dqs) + 2:
                #isj = mult_table(mc, dqs, j_l[0], len(dqs)-j_r[0], sorted_indices)
                isj = mult(dqs[j_l[0] : len(dqs) - j_r[0] ])
                #print j_l[1], isj, j_r[1], j_l[1] * isj * j_r[1]
                if j_l[1] * isj * j_r[1] == -q('1'):
                    return "YES"
                # else:
                #     j_left = mult(dqs[j_l[0] : -1])
                #     j_right = mult(dqs[0 : len(dqs) - j_r[0]])
                #     j_middle = q('1')
                #     for k_d in range(min(X - 8, 4)):
                #         j_middle = j_middle * mfqs
                #         if j_l[1] * j_left * j_middle * j_right * j_r[1] == -q('1'):
                #             return "YES"

    return "NO"

for i in range(T):
    L, X = map(int, fin.readline().split())
    ijk = fin.readline()
    solution = solve(L, X, ijk)
    # if solution > candidate:
    #     print 'ERROR', i + 1, solution, candidate
    # if solution != solution1:
    #     print 'ERROR', i + 1, solution, solution1, candidate
    answer = "Case #%d: %s\n" % (i + 1, solution)
    print answer
    fout.write(answer)

fin.close()
fout.close()
# f1out.close()
# f2out.close()

D. Ominous Omino

종이랑 펜은 꼭 준비해 두기.

문제 속에 hint가 있었다. 7-ominous 이상에서는 richard가 승리한다는 것.

brute force로도 풀 수 있는 문제였다.

small input에 대해서 if 몇 개로 풀 수 있었는데, 이런 문제가 나올 줄은 예상 못해서 좀 어색했네.

large input은 틀리고 말았다 T_T 지그재그 case를 틀렸나 보다.

import math

sample = "sample"
small = "D-small-attempt5"
large = "D-large"
current = large

fin = open(current + ".in", "r")
fout = open(current + ".out", 'w')
# f1out = open(current + "1.out", 'w')
# f2out = open(current + "2.out", 'w')

T = int(fin.readline())

Gabriel = "GABRIEL"
Richard = "RICHARD"

def solve(X, R, C):
    if (R * C) % X != 0:
        print "%"
        return Richard
    if R < X and C < X:
        print "<"
        return Richard
    if X > 6:
        print "6"
        return Richard
    min_l = 1 + (X - 1) / 2
    if X > 2 and (R < min_l or C < min_l):
        print "sqrt"
        return Richard
    snake = 2 + (X - 2) / 3
    if X > 3 and (R <= snake or C <= snake):
        print "snake"
        if X == 4:
            return Richard
        elif X == 5 and (R < 5 and C < 5):
            return Richard
        elif X == 6 and (R < 7 and C < 7):
            return Richard

    return Gabriel

for i in range(T):
    X, R, C = map(int, fin.readline().split())
    print i+1, X, R, C

    solution = solve(X, R, C)
    # if solution > candidate:
    #     print 'ERROR', i + 1, solution, candidate
    # if solution != solution1:
    #     print 'ERROR', i + 1, solution, solution1, candidate
    answer = "Case #%d: %s\n" % (i + 1, solution)
    print answer
    fout.write(answer)

fin.close()
fout.close()
# f1out.close()
# f2out.close()

27시간 안에 20점을 넘어야 통과

A, D만 먼저 풀었으면 금방 안심은 했을텐데.

2747

Me

53

23:07:43

7:20:42

7:21:25

-- 12 wrong tries

--

20:27:42  3 wrong tries

20:56:41

22:35:43  5 wrong tries

-- 1 wrong try