Code Jam Japan2011 練習問題A. 数珠繋ぎ (Small) 解いた

概要

気分転換にCode Jam Japan2011の練習問題A(問題A. 数珠繋ぎ)を解いたので、書いたスクリプトを晒してみる.

イメージ

ステップごとのイメージが文章を読んでるだけじゃ、わからなかったので、スライド作った。

Code jam japan2011 練習問題A

View more presentations from Kshi_Kshi

スクリプト(Python)

#!/usr/bin/env python
# coding: utf-8
# vim: fileencoding=utf8

import sys
import re

class Socket(object):
    def __init__(self):
        self.switch = "OFF"

    def change(self):
        if self.switch == "OFF":
            self.switch = "ON"
        else:
            self.switch = "OFF"


class Sockets(object):
    def __init__(self, N):
        self.N = N
        self.sockets = []
        for i in range(N):
            self.sockets.append(Socket())

    def change(self):
        for i in range(self.N):
            if self.sockets[i].switch == "OFF":
                break
        while(i >= 0):
            self.sockets[i].change()
            i -= 1
        #self._debug_print_sockets()

    def judge(self):
        status_set = set([socket.switch for socket in self.sockets])
        if len(status_set) == 1 and "ON" in status_set:
            return "ON"
        return "OFF"

    def _debug_print_sockets(self):
        for i in range(self.N):
            print i,self.sockets[i].switch
        print '-------------------------------'


def read_input_data(file_name):
    try:
        file_obj = file(file_name, 'r')
        length = file_obj.readline().rstrip('\r\n')
        return True, length, \
            [map(int, re.compile(u' ').split(line.rstrip('\r\n'))) for line in file_obj]
    except IOError:
        print 'FILE NOT FOUND: ' + str(file_name)
        return False, None, None


if __name__ == '__main__':
    input_file = './A-small-practice.in'
    #input_file = './A-large-practice.in'

    read_judge, length, dataset = read_input_data(input_file)
    if not read_judge: sys.exit()

    case = 1
    for data in dataset:
        N = data[0]
        K = data[1]
        status = Sockets(N)
        while(K>0):
            status.change()
            K -= 1
        print "Case #%s: %s" %(case, status.judge())
        case += 1

感想

とりあえず、効率を考えないでやってみたが、当然largeのデータセットは計算が終わりそうになかった。
smallとlargeのデータセットを用意しているのは、さすがプログラミングコンテストだなと思った。

最近、DevQuizから、こういうプログラミングの問題を解くのが楽しい。

次は、このアルゴリズムを改良してlargeデータセットにも対応できるものにしようと思っている。(次回の気分転換にでも)
本番まで、残り2週間か、せめて練習問題3問くらいはやっておきたい。

参加登録がまだな人は登録しましょう！

Google Code Jam Japan 2011