밝은 미래

첫 문제는 쉬웠다.

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

알고리즘은 금방 생각할 수 있었다.

같은 진법에서 102345... 같은 숫자가 가장 작다.

가장 적은 수 진법일 때 가장 작다.

처음에는 ruby input, output 처리에 시간이 걸렸다.

특별한 case 처리를 잘 못해서 small input에서 답을 틀렸다.

111 일 때, 2진법 숫자인데, 1진법 숫자라고 계산해 버렸다.

어떤 case에서 왜 틀렸는지 찾는 것에 1시간 걸렸다 T_T

역시, 처음, 끝 값 등에 대한 처리는 다시 한 번 확인해보고, unit test를 하는 게 좋겠다.

총 2시간 쯤 걸렸던 것 같다.

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

SAMPLE = 'sample.in'
SMALL = 'A-small-practice.in'
LARGE = 'A-large-practice.in'

input = File.open(LARGE)
output = File.open('./out.txt', 'w')
$log = File.open('./log.txt', 'w')

class AliensMinDday

  def initialize(numberText)
    @numberHash = Hash.new
    @numberText = numberText.gsub("\n", '')

    order = 0
    @numberText.split("").each do |c|
      if @numberHash[c] == nil then
        @numberHash[c] = order
        order += 1
      end
    end
  end

  def solve()

    base = @numberHash.count()
    if base == 1 then
      base = 2
    end
    result = 0

    index = @numberText.length - 1

    $log.write "\n"
    $log.write @numberText
    $log.write "\n"

    @numberText.split("").each do |c|
      number = @numberHash[c]
      if number == 0 then
        number = 1
      elsif number == 1 then
        number = 0
      end

      result += number * (base ** index)

      $log.write "#{number}"

      index -= 1

    end
    $log.write " #{base}\n"

    result

  end

end


count = input.readline()
iCase = 0
input.read.each_line do |line|
  iCase += 1
  answer = AliensMinDday.new(String.try_convert(line)).solve()
  output.write "Case ##{iCase}: #{answer}\n"
  $stdout.write "\n#{line} Case ##{iCase}: #{answer}\n"
end

vector 연산으로 center of mass, average velocity를 쉽게 구할 수 있었다.

ruby에서 vector 기능을 찾는 것에 한참의 시간을 소비했다. 30분 이상?

나중에 알고 보니, python 상위권 입상자들은 vector 연산을 손으로 구현했더라 -0-

막상 center of mass까지는 쉽게 구했는데, 최단 거리일 때의 시간을 구하는 것은 잠깐 막막했다.

시작할 땐, 막연하게 될 것 같았는데, code로 만들으려니까 될지 말지도 의심이 되더라.

종이에 vector 수식을 세우고서 쉽게 된다는 것을 알았다. 역시, 종이에 써가면서 풀어야 하겠다.

이것도 한 번에 small input을 통과하지 못 했다.

특별한 case를 생각하지 못했다.

print해 놓은 log를 보니, 틀린 부분을 찾을 수 있었다. 시간이 음수인 상황이 있었다.

center of mass가 원점으로부터 멀어지는 경우. 이 경우에는 t = 0

또 1시간 헤맸다..

총 3시간 쯤 걸렸으려나.

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

require "matrix"

$log = File.open('log.txt', 'w')

class CenterOfMass

  def initialize
    @rows = Array.new
  end
  def append(data)
    vector = Vector.elements(data.split(' ').map { |e| e.to_f })
    #puts vector
    @rows.push vector
  end

  def solve
    #puts @rows
    sum = Vector[0, 0, 0, 0, 0, 0]
    @rows.each {
      |row|
      #puts row, sum
      sum = sum + row
    }
    averageRow = sum / @rows.count
    # puts @rows
    # puts sum

    # puts averageRow
    center = Vector.elements(averageRow[0..2])
    velocity = Vector.elements(averageRow[3..5])

    if velocity.r > 0.00000001 then
      minTime = - velocity.inner_product(center) / velocity.inner_product(velocity)
    else
      minTime = 0
    end

    if minTime < 0 then
      minTime = 0
    end

    distance = center + velocity * minTime
    puts minTime, center, velocity, distance

    return distance.magnitude, minTime

  end
end

sample = 'sample.in'
small = 'B-small-practice.in'
large = 'B-large-practice.in'
out = 'out.txt'
input = File.open(large)
output = File.open(out, 'w')


count = input.readline()
iCase = 0
while true
  iCase += 1

  nFlies = input.readline()
  break if input.eof?



  nFlies = nFlies.to_i
  mass = CenterOfMass.new
  nFlies.times {
    data = input.readline()
    mass.append(data)
  }

  # if iCase > 11 && iCase < 16 then
    solution = mass.solve
    # puts solution[0], solution[1]
    output.write "Case ##{iCase}: #{solution[0]} #{solution[1]}\n"
  # end
end

2가지 알고리즘을 생각했다.

첫 번째 알고리즘으로, 매번 가운데에서 가까운 prisoner를 석방해가면서 문제를 쪼개가면 풀 수 있다고 생각했다.

small input에서 틀리고서.. 2번째 알고리즘으로 다시 풀었다.

문제를 subproblem으로 쪼개면서 풀되, dynamic programming으로 시간을 절약하기.

dynamic programming을 하지 않고, 모든 case에 대해 다 쪼갠다면, small input은 풀 수 있겠다.

dynamic programming으로도 large input까지 풀 수 있다는 확신은 없이 시작했다. 첫 알고리즘이 틀리는 case를 찾으려고, 비교용으로 구현한 셈.

두 결과를 비교해 보고, 결과가 틀린 부분에서 debugging을 했다.

dynamic programming이 더 optimal한 결과를 냈다.

첫 번째 알고리즘은 그제서야 파기 T_T

이 경우에 dynamic programming을 효율적으로 쓰려면,

1 5 [3, 4] case와 2 6 [4, 5] 가 같은 case라고 인식하도록 하는 게 좋겠다.

2 6 [3, 4] 도 같은 case라고 인식하게 만들면 좋겠지만, 여기까지는 못했다.

횡으로 translation을 하되, parameter로 넘길 때는 알아보기 쉽도록 원본 input scale을 썼다.

recursive function에서 결과로 어떤 과정이었는지 debugging용 string도 return하게 만들고, 실행 시점에는 ""로 대체했다.

large input을 실행시켰더니, 컴퓨터가 먹통이 된다 -_-

python ide로 canopy는 안되겠다. windows도 쓸 만한 os는 아닌 것 같다.

처음에는 메모리를 쓰더라도 계산을 빨리 하려고, dynamic programming table을 global로 1개를 썼다.

ide를 jetbrains pycharms로 바꾸고,

print문을 없애고, table을 매 case 생성하는 것으로 바꿨더니, large input에서 case 별 1초 정도 걸리는 것 같다.

총 5시간 가까이 걸렸으려나 T_T

import sys
import os

sample = "sample"
small = "C-small-practice"
large = "C-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')

#sys.stdout = open(os.devnull, 'w')

T = int(fin.readline())

def bribe(rs, s, e):
    if not rs:
        return 0
    if s >= e:
        return 0
    center = (s + e) / 2.0
    closest = e + 2
    for i in rs:
        if abs(center - i) < abs(center - closest):
            closest = i
    
    left = [a for a in rs if a < closest]
    right = [a for a in rs if a > closest]
    print s, e, closest, e - s, left, right
    return (e - s) + bribe(left, s, closest - 1) + bribe(right, closest + 1, e)
    
solutions = {}
def dynamic_bribe(rs, s, e, space):
    if not rs:
        return "", 0
    if s >= e:
        return '', 0
    
    s0 = 1
    e0 = e - s + 1
    rs0 = [a - s + 1 for a in rs]
    
    key = str(e0) + ':' + (',').join(str(a) for a in rs0)
    keystr = str(s) + '~' + str(e) + ':' + (',').join(str(a) for a in rs)
    solution = solutions.get(key)
    if solution:
        #print space, s, e, rs, solution, "key:" + key
        #return '\n' + space + '<' + keystr + '_' + str(solution) + '>\n', solution
        return '', solution
    else:
        candidate = sys.maxint
        way = ""
        for r in rs:
            left = [a for a in rs if a < r]
            right = [a for a in rs if a > r]
            left_way, lc = dynamic_bribe(left, s, r-1, space + '   ')
            right_way, rc = dynamic_bribe(right, r+1, e, space + '   ')
            cc = (e - s) + lc + rc
            if cc < candidate:
                candidate = cc
                way = '\n' + space + '<' + keystr + '_' + str(cc) + ',' + left_way + ',' + right_way + '>\n'
        solution = candidate
        solutions[key] = solution
        #print space, s, e, rs, solution
        #return way, solution
        return '', solution
        
#print dynamic_bribe([3], 1, 8, '')

def solve(P, Q, rs):
    a = bribe(rs, 1, P)
    #print ''
    
    #if a != b:
    #    print "DIFFERENT", a, b, a > b
    
    return a
    
def dynamic_solve(P, Q, rs):
    way, b = dynamic_bribe(rs, 1, P, '')
    print way
    return b
    
cases = [15]

for i in range(T):
    #if i > 3:
    #    break
    solutions = {}
    P, Q = map(int, fin.readline().split())
    rsline = fin.readline()
    rs = map(int, rsline.split())
    
    #if i in cases:
    if True:
        print P, Q, rs
        #answer = solve(P, Q, rs)
        #line = "Case #%d: %s" % (i+1, str(answer))
        #print line + '; ' + rsline + '\n'
        #f1out.write(line + '\n')
        
        answer2 = dynamic_solve(P, Q, rs)
        line2 = "Case #%d: %s" % (i+1, str(answer2))
        print line2 + '; ' + rsline + '\n'
        fout.write(line2 + '\n')
    
fin.close()
fout.close()
f1out.close()
f2out.close()

#sys.stdout = sys.__stdout__