Code Jam Japan2011 練習問題C. 遊園地 (Small) 解いた
概要
また、息抜きがてら、Code Jamの練習問題をしたので、コードを晒してみる.
やった問題は、問題C. 遊園地
Bのlargeは未だ放置中。
Pythonスクリプト
#!/usr/bin/env python # coding: utf-8 # vim: fileencoding=utf8 import sys import re def read_input_data(file_name): try: file_obj = file(file_name, 'r') total = int(file_obj.readline().rstrip('\r\n')) dataset = [] for i in range(total): element = map(int, re.compile(u' ').split(file_obj.readline().rstrip('\r\n'))) element.append(map(int, re.compile(u' ').split(file_obj.readline().rstrip('\r\n')))) dataset.append(element) return True, total, dataset except IOError: print 'FILE NOT FOUND: ' + str(file_name) return False, None, None class GroupList(object): def __init__(self, G): self.G = G self._next_index = 0 def __iter__(self): return self def next(self): val = self.G[self._next_index] used_index = self._next_index # if next index is nothing ,then next index is first index. if len(self.G) == (self._next_index + 1): self._next_index = 0 else: self._next_index += 1 return val, used_index def get_val(self, index): return self.G[index] class Status(object): def __init__(self, R, K, GL): self.R = R self.K = K self.GL = GL def run(self): used_indexes_set = set() now_passenger = 0 total_passenger = 0 while self.R > 0: while True: next_val, used_index = self.GL.next() # check limit of seat if now_passenger + next_val > self.K: # case: over capacity for index in used_indexes_set: # calculate num of passenger on this time total_passenger += self.GL.get_val(index) # initilize now_passenger = next_val used_indexes_set = set([used_index,]) break # run roller coaster else: # case: enable to ride # add passenger information now_passenger += next_val used_indexes_set.add(used_index) self.R -= 1 return total_passenger if __name__ == '__main__': input_file = './C-small-practice.in' #input_file = './C-large-practice.in' read_judge, total, dataset = read_input_data(input_file) if not read_judge: sys.exit() for i in range(total): R = dataset[i][0] # count: number of running a day K = dataset[i][1] # seat: capacity of roller coaster #N = dataset[i][2] # Not Used G = dataset[i][3] # Group List GL = GroupList(G) # Create Modified Iterator Object status = Status(R, K, GL) print "Case #%s: %s" %(i+1, status.run())
感想
∞リストみたいなものをクラスを使って独自で定義したが、ジェネレーターというものを使えば、もっとスマートに書けたみたい。そのうちジェネレータも書いてみる予定。
一回一回ジェットコースターが全て回りきるまでの状態を見ている感じで書いたので、当然、Largeのデータセットは終わらない様子だった。
グループの周期性を利用すればいいのかな〜と思っているが、さていい感じの時間で解けるものが作れるのかはまだ、不明。
丁度1週間後が本番なので、それまでに練習問題BとCのLargeにチャレンジしようと思っている。Aの問題もコードをリファクタリングする話をしたはいいが、実はまだやってないので、そのエントリーにも終止符を打ちたい。今日この頃である。
