Code Jam Japan2011 練習問題A. 数珠繋ぎ (Large) 解いた
内容
前回作成したアルゴリズムでは、12時間以上放置しても計算が終わらなかった。
そりゃそうか、状態の遷移を毎ターン律儀に行うような形だったし。
ということで、現実的な計算時間で解けるようにしないといけない。
このような問題を解くために2種類のアプローチがあるかな〜っと思ったので、その2種の方法で試してみた。
- 1つ目は、問題の法則をモデルに落とし込む数学的アプローチ.（数学的とか言うと大袈裟な気もするけど・・・）
- 2つ目は、現状のアルゴリズムをベースに改善するアプローチ.
数学的なアプローチで解を一発で求められるようなことが実現できるのが理想的だが、現実の問題ではそう簡単に、最適な解(アルゴリズム)を得るのは難しいのではないかと思ったので、実際の動いているコード(前エントリーで晒したスクリプト)の無駄な個所を改善するようなこともしてみることに。(リファクタリングの練習として。)
数学的なアプローチ
N=1の場合、電球がONになるKは k=1,3,5,7,9,11,13,15,17...の時。周期は2
N=2の場合は、k=3,7,11,15...の時。周期は4
N=3の場合は、k=7,15...の時。周期は8
N=4の場合は、k=15,おそらく、今までの規則性からONになる周期は単純にN^2 だろうと推測でき、この場合の周期は16で次ONになるのはk=31の時だろうと思ったので、以下のように書いてみた。
#!/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')) return True, total, \ [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 def _get_cycle(N): return pow(2, N) def answer(N, K): cycle = _get_cycle(N) if(K % cycle == cycle-1): return "ON" return "OFF" if __name__ == '__main__': #input_file = './A-small-practice.in' input_file = './A-large-practice.in' read_judge, total, dataset = read_input_data(input_file) if not read_judge: sys.exit() for i in range(total): N = dataset[i][0] # number of sockets K = dataset[i][1] # step times print "Case #%s: %s" %(i + 1, answer(N, K))
出力データを送信し確かめたら、正解だった。
任意のN,Kでも計算量はで一定なので、負荷の予測も立てやすくこの解が理想的なのではないかなと思う。
前回のアルゴリズムをベースに改善するアプローチ
理想的な解法が先にできてしまい、モチベーションがアレだったが、リファクタリングの練習として、気合いを入れてやってみることに。
前回のアルゴリズムの改善点としては、
- 周期性を利用してない. -> 周期性の利用.
- 既存のNについての結果を活かせていない. -> 現状で求めてあるNの最大の結果を利用して計算量を減らす.
などが考えられたので、Nに対する周期を求め、その周期を使ってONかOFFかを判断し、その周期をキャッシュさせてみたらいい感じになるのではと思い書いてみた。
#!/usr/bin/env python # coding: utf-8 # vim: fileencoding=utf8 import sys import re def read_input_data(file_name): # 上と同じ関数 pass class Sockets(object): CYCLE_DATA = {} # class member #{1: CYCLE_1, 2: CYCLE_2, 3: CYCLE_3, ... , N: CYCLE_N} def __init__(self, N, K): self.N = N self.K = K def _calculate_cycle(self, n): # initialize sockets if (n==1): sockets = [0] now_step = 0 else: sockets = [0,] * (n-1) + [1,] now_step = self.CYCLE_DATA[n-1] #print "\t\tINITIALIZE sockets:", sockets # 点灯するまで状態を遷移させる while(True): for i in range(n): if sockets[i] == 0: break while(i >= 0): # 符号を反転させる if sockets[i] == 0: sockets[i] = 1 else: sockets[i] = 0 i -= 1 now_step += 1 # 点灯するかどうかをチェック if self._judge(sockets): self.CYCLE_DATA[n] = now_step + 1 #print "\tGET CYCLE:", n, "->", self.CYCLE_DATA[n] return None def _judge(self, sockets): status_set = set([socket for socket in sockets]) if len(status_set) == 1 and 1 in status_set: return True return False def _get_cycle(self): if self.N in self.CYCLE_DATA.keys(): # case: exisiting N -> using cache #print "\tUsed Cache:" , self.N, "->", self.CYCLE_DATA[self.N] pass else: # case: new N # calculate cycle if len(self.CYCLE_DATA) == 0: searching_N = 1 else: searching_N = max(self.CYCLE_DATA.keys()) + 1 # 既存のMAX周期 ~ Nまでの周期を計算 while (searching_N <= self.N): self._calculate_cycle(searching_N) searching_N += 1 return self.CYCLE_DATA[self.N] def answer(self): cycle = self._get_cycle() if(self.K % cycle == cycle-1): return "ON" return "OFF" if __name__ == '__main__': #input_file = './A-small-practice.in' input_file = './A-large-practice.in' read_judge, total, dataset = read_input_data(input_file) if not read_judge: sys.exit() for i in range(total): N = dataset[i][0] # number of sockets K = dataset[i][1] # step times status = Sockets(N, K) print "Case #%s: %s" %(i+1, status.answer())
感想
前回のコードをリファクタリングするアプローチでは、キャッシュしたり、できるだけ前の計算した状態になるところから遷移をするようにすることで、計算効率を約10倍以上改善させることができたが、改善後のアルゴリズムでもNが30個になると2の30乗=1073741824までのソケットの遷移を少なくとも一回確認する必要があるために、（それ以降はキャッシュする。）
現実的な時間で実行を終わらせることができなかった。このコンテストではLargeを計算できる時間が限られているため数学的により計算量を少なくするようなアプローチでやらないとLargeは解けないのだろうと感じた。でもキャッシュは強いことを確認できた。
