気分転換に競技プログラミング: Google Code Jam Qualification Round 2012: Problem C. Recycled Numbers

概要

今日免許の更新に行ってきた。
過去2回の違反(通行禁止違反、進路変更禁止違反)により違反運転者講習に区別され、２時間に渡って大変わかりやすい講習を受けてきた。
講習中余ったリソースを用いて、Google Code Jam Qualification Round 2012 Problem C. Recycled Numbers について考えていたわけだが、その時のアイディアを帰宅後にコード化したものを晒す。まだlargeは解けていないが...

solve.py

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

"""
Google Code Jam
Qualification Round 2012
Problem C. Recycled Numbers
http://code.google.com/codejam/contest/1460488/dashboard#s=p2
"""

import sys

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(" ")
    A = int(line.pop(0))
    B = int(line.pop(0))

    def reverse_patterns(num):
        str_num = str(num)
        patterns = {}
        for i in range(1, len(str_num)):
            s1 = str_num[:i]
            s2 = str_num[i:]
            if s1.startswith("0") or s2.startswith("0"):
                continue
            r_num = int(s2 + s1)
            if num == r_num:
                continue
            elif A <= r_num <= B:
                patterns.setdefault(r_num, 0)
        return patterns.keys()

    pairs = {}
    num_set = [n for n in range(A, B+1)]
    for num in num_set:
        for r_num in reverse_patterns(num):
            pair = tuple(sorted([num, r_num]))
            pairs.setdefault(pair, 0)
    return len(pairs.keys())

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

if __name__ == "__main__":
    main()