밝은 미래

첫 문제는 쉬웠다.

보통 이건 잘 푸는 것 같다. 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()

여기서 완전 말렸다.

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

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

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

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

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

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()

문제 속에 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()

흑, large input은 실패했다. small input 푸는 것만 3시간은 걸렸다. 사소한 실수를 좀 많이 했다.

performance 계산을 안해보고, 대충 연습을 시작해 본 것도 문제였다. large input은 못 푸는 algorithm을 너무 오랜 시간 동안에 구현해냈네.

한 가지 착안한 것은 공통의 자릿수가 바뀐다는 점이었다.

그것으로 다음 수들이 나오려면, 같은 자리 수에는 outlet과 plug에 대해서 1과 0의 개수가 같아야만 하겠다.

이것으로 문제가 풀릴 것 같은 좋은 예감으로 시작했는데,,

1과 0의 개수가 같은 경우에는 모든 경우의 수에 대해서는, flip이 발생했는지, 발생하지 않았는지를 알 수가 없었다..

brute force로 풀어야만 했다.

brute force만으로 2^n인 것을 random input에 대해서 평균적으로 2^(n-c) (?) 정도로 줄였는데, c가 너무 작아서 large input에서는 쓸모가 없었다.

brute force로 flipping하는 것을 flip, sort 횟수가 적도록 해볼 수 있을 것만 같았는데, 좋은 구현 방법을 생각해 내지 못했다.

포기..

나중에 해답을 보고 알았는데, 진짜 풀이 방법의 point는 그런 게 아니었다.

난 outlet을 switch해가면서 plug를 만들려고 했지만,

풀이는 plug가 나올 수 있는 모든 경우의 수를 n^2개 미리 나열해버리고, outlet을 맞춰 보는 방법인가 보다.

(맞게 이해한 건가..)

어쨋거나 거꾸로 생각해 보는 것도 좋은 시도인 것 같다.

# https://code.google.com/codejam/contest/2984486/dashboard

import sys
import os
#import numpy as np
import itertools

sample = "sample"
small = "A-small-practice"
large = "A-large-practice"
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(outlets, plugs, N, L):
    #print outlets, plugs
    plugs.sort()

    shuffle = []
    switch = []
    unknown = []
    for i in range(L):
        ips = [(p >> i) % 2 for p in plugs]
        ios = [(o >> i) % 2 for o in outlets]
        print i, ips, ios
        if ips.count(1) == ios.count(1):
            if ips.count(1) == ips.count(0):
                unknown.append(i)
        elif ips.count(0) == ios.count(1):
            if ips.count(1) == ips.count(0):
                unknown.append(i)
            else:
                shuffle.append(i)
        else:
            return "NOT POSSIBLE"


    shuffled_outlets = outlets[:]
    for s in shuffle:
        shuffled_outlets = [o ^ pow(2, s) for o in shuffled_outlets]

    print outlets, "-->", shuffled_outlets, shuffle, unknown
    shuffled_outlets.sort()

    result = len(shuffle)
    print plugs
    print shuffled_outlets

    if plugs == shuffled_outlets:
        return str(result)

    for i in range(len(unknown)):
        for j in itertools.combinations(unknown, i+1):
            shuffled_outlets2 = shuffled_outlets[:]
            for k in j:
                shuffled_outlets2 = [o ^ pow(2, k) for o in shuffled_outlets2]
            shuffled_outlets2.sort()
            #print shuffled_outlets
            if plugs == shuffled_outlets2:
                return str(result + i + 1)

    return "NOT POSSIBLE"

for i in range(T):
    N, L = map(int, fin.readline().split())
    outlets = [int(n, 2) for n in (fin.readline().split())]
    plugs = [int(n, 2) for n in (fin.readline().split())]
    print 'o', outlets
    print 'p', plugs
    solution = solve(outlets, plugs, N, L)
    if N == 1 and solution == "NOT POSSIBLE":
        print "ERROR1"
    if solution != "NOT POSSIBLE" and N < int(solution):
        print "ERROR2"
    answer = "Case #%d: %s\n" % (i+1, solution)
    print answer
    fout.write(answer)



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

A는 2012년 당시보다 매우 쉽게 정석대로 풀었다.

수식만 세우고, 필요한 계산만 하면 쉽게 풀렸다.

1시간도 안 걸렸던 것 같다.

B는 문제를 제대로 이해 못해서 한참 헤맸다.

sample input은 쉽게 통과했는데, 로직에 틀린 부분이 있어서 small input 푸는 것에 시간을 많이 보냈다.

틀린 부분을 못 찾고, 3시간 이상 걸려서 답 안 보고 푸는 것은 포기했다.

B-small-practice.out 을 github에서 찾아내고, 틀린 test case를 diff로 찾았다.

손으로 푼 결과랑 비교할 수 있게 로그를 남겼다.

답 등을 graph로 남겨서 변화를 알기 쉽게 만드는 것도 도움이 되겠다.

C는 무리다..

L, R 무시하고, 수식으로 풀 수 있을 것 같았는데, 머리가 잘 안 돌아간다.

해답을 보니, 수식만으로 푼 것 같지도 않다. 나중에 시간이 날 때, 해답을 읽어보고 다시 풀어봐야 하겠다.

L, R이 주어진 만큼, 이용을 해서 풀어야 하겠다.

#https://code.google.com/codejam/contest/1645485/dashboard

import sys
import os

sample = "sample"
small = "A-small-practice"
large = "A-large-practice"
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(typed, N, ps):
    acc_ps = []
    acc_p = 1
    for p in ps:
        acc_p *= p
        acc_ps.append(acc_p)

    ss = []
    for b in range(typed):
        strokes = acc_ps[typed - b - 1] * (N - typed + 2 * b + 1) + (1 - acc_ps[typed - b - 1]) * (N - typed + 2 * b + 1 + N + 1)
        ss.append(strokes)

    ss.append(2 + N)

    return min(ss)

for i in range(T):
    typed, N = map(int, fin.readline().split())
    ps = map(float, fin.readline().split())

    solution = solve(typed, N, ps)
    answer = "Case #%d: %s" % (i+1, str(solution))
    fout.write(answer + '\n')

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

# https://code.google.com/codejam/contest/1645485/dashboard#s=p1

import sys
import os
import numpy as np

sample = "sample"
small = "B-small-practice"
large = "B-large-practice"
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())


completed = []
star1s = []
sorted_star2_indices = []

def next_rush1(score):
    global star1s
    global sorted_star2_indices
    global completed

    if not sorted_star2_indices:
        return -1

    for level in reversed(sorted_star2_indices):
        if (not completed[level]) and star1s[level] <= score:
            return level

    return -1

def next_challenge():
    global star1s
    global sorted_star2_indices
    global completed

    if not sorted_star2_indices:
        return -1

    return sorted_star2_indices[0]

def rush1(level, stars, score):
    global star1s
    global sorted_star2_indices
    global completed

    if level >= 0:
        completed[level] = True
        next = next_challenge()
        # print 'rush1+1', level, score, completed, sorted_star2_indices, next
        n_moves, more_scores = rush(next, stars, score + 1)
        return 1 + n_moves, 1 + more_scores

    return 0, -1

def rush(level, stars, score):
    global star1s
    global sorted_star2_indices
    global completed

    if stars[level][1] <= score:
        sorted_star2_indices.remove(level)
        if completed[level]:
            # print 'rush2+1', level, score, completed, sorted_star2_indices, stars[level][1]
            return 1, 1
        else:
            # print 'rush2+2', level, score, completed, sorted_star2_indices, stars[level][1]
            return 1, 2

    return rush1(next_rush1(score), stars, score)

def greater(a, b):
    global star1s

    if a[1] > b[1]:
        return 1
    elif b[1] > a[1]:
        return -1

    return star1s[b[0]] - star1s[a[0]]

def solve(n_stars, stars):
    global star1s
    global sorted_star2_indices
    global completed

    n_moves = 0
    total_score = 0
    star1s = np.array(stars).T[0]
    star2s = np.array(stars).T[1]

    #sorted_star2_indices = [v[0] for v in sorted(enumerate(star2s), key=lambda x:x[1])]
    sorted_star2_indices = [v[0] for v in sorted(enumerate(star2s), cmp=greater)]
    sorted_star2_values = [v[1] for v in sorted(enumerate(star2s), cmp=greater)]

    # print ""
    # print star1s
    # print star2s
    # print sorted_star2_indices
    # print sorted_star2_values

    while sorted_star2_indices:
        level = next_challenge()
        move, more_scores = rush(level, stars, total_score)
        if move <= 0:
            return 0, -1
        n_moves += move
        total_score += more_scores
    return n_moves, total_score

for i in range(T):
    N = int(fin.readline())
    stars = []
    completed = []
    for j in range(N):
        stars.append(map(int, fin.readline().split()))
        completed.append(False)

    solution, score = solve(N, stars)
    solutionText = str(solution) if (solution > 0) else "Too Bad"
    answer = "Case #%d: %s" % (i+1, solutionText)
    fout.write(answer + '\n')

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