気分転換に競技プログラミング: Google Code Jam Qualification Round 2012: Problem B. Dancing With the Googlers

また研究からの現実逃避をした

ゼミ後に後輩と一緒に Code Jam の問題で楽しんだので気分転換したので、コードを晒してみる。
やった問題は Problem B. Dancing With the Googlers 。

しかし、アルゴリズムがカスでLargeのデータセットは解けずにいる。
また気が向いた時に改良する予定。

#!/usr/bin/env python
# coding: utf-8

"""
Google Code Jam
Qualification Round 2012
Problem B. Dancing With the Googlers
http://code.google.com/codejam/contest/1460488/dashboard#s=p1
"""

import sys
import itertools

def read():
    f = sys.stdin
    num = int(f.next().strip())
    return [f.next().strip() for i in range(num)]

def solve(case):
    line = case.split(" ")
    N = int(line.pop(0))
    S = int(line.pop(0))
    P = int(line.pop(0))
    T = map(int, line)

    def check_triple(num, S_flg):
        a = int(num / 3)
        r = num % 3 # remainder
        def get_s_triple():
            if r == 0: return (a-1, a, a+1)
            elif r == 1: return (a-1, a+1, a+1)
            elif r == 2: return (a, a, a+2)
        def get_not_s_triple():
            if r == 0: return (a, a, a)
            elif r ==1: return (a, a, a+1)
            elif r ==2: return (a, a+1, a+1)
        if S_flg:
            triple =  get_s_triple()
        else:
            triple = get_not_s_triple()
        for _p in triple:
            if _p < 0: return 0
            if _p >= P: return 1
        return 0

    answer_set = []
    for S_indexes in itertools.combinations(range(N), S):
        pattern = []
        for i in range(N):
            if i in S_indexes:
                S_flg = True
            else:
                S_flg = False
            pattern.append(check_triple(T[i], S_flg))
        answer_set.append(sum(pattern))
    return max(answer_set)

def main():
    dataset = read()
    for i, case in enumerate(dataset):
        answer = solve(case)
        print "Case #%d: %d" % (i+1, answer)

if __name__ == "__main__":
    main()

英語の問題、問題を理解するのに一苦労。
続けていけば、きっと明るい未来がまってるはず。
また近いうちに現実逃避します。