Code Jam Japan 2011挑んだ- > かろうじて予選通過
概要
以前から参加を表明していたCode Jam Japan 2011の予選にフルタイム(6時間)挑んだので、提出したコードとかを晒してみる。
結果
23点の493位だった。予選はギリギリ通過することができた。
問題 A small & large パス。
問題 B smallに挑戦したが、時間内に正解データを出力することができなかった.
問題 C smallのみ正解。largeはいい解法が思い浮かばなかったので未着手。
問題A. カードシャッフル
問題へのリンク
最初は、配列を使ってシャッフルのたびにカードの状態を保持するように新しい配列を生成するように実装した。Largeでは要素数10^9個の配列をシャッフルするたびに生成するこの手法では制限時間内に処理が終わらないだろうと思い、配列を使わない手法を3時間ほど悩んでできたのが以下のコード。
#!/usr/bin/env python # coding: utf-8 # vim: fileencoding=utf8 import re import sys def read_input_data(file_name): try: file_obj = file(file_name, 'r') total = int(file_obj.readline().rstrip('\r\n')) dataset = {} all_C_info = {} for i in range(total): element = map(int, re.compile(u' ').split(file_obj.readline().rstrip('\r\n'))) all_C_info[i] = [] for j in range(element[1]): # element[1] : C all_C_info[i].append(map(int, re.compile(u' ').split(file_obj.readline().rstrip('\r\n')))) dataset[i] = element return True, total, dataset, all_C_info except IOError: print 'FILE NOT FOUND: ' + str(file_name) return False, None, None if __name__ == '__main__': #input_file = './A-small.in' input_file = './A-large.in' read_judge, total, dataset, all_C_info = read_input_data(input_file) if not read_judge: sys.exit() for i in range(total): W = dataset[i][2] # nth card who want to know after cards will be shuffled c_info = all_C_info[i] # shuffle information now_index = long(W) for (An, Bn) in c_info[::-1]: if Bn >= now_index: # ① now_index = now_index + An -1 else: if (An+Bn-1) >= now_index: # ② now_index -= Bn else: # ③ pass print "Case #%s: %s" %(i+1, now_index)
主にやっていることは、最終的に知りたいインデックスが最初の何番目にあるのかを最後のシャッフルからインデックスのみを遡って追っていくような感じで書いた。配列は使わないので、計算量はシャッフルの回数のみで済むのでとても高速な解放ではないかと思っている。
詳細のアルゴリズムの内容は、
- 現在のインデックス: now_index
- 一つ前(交換する前)のインデックス: before_index
- 交換開始するインデックス: An
- 交換枚数: Bn
before_indexからnow_indexに変わるのは以下の3パターン
① before_indexが交換範囲(An <= before_index < An+Bn)になっている場合 => 交換範囲が先頭に来るので、交換後のインデックスは交換範囲の何番目だったかを求めればよい.
now_index = before_index - An + 1
② before_indexが交換範囲より前にあった場合 => 交換後のインデックスは交換した枚数文後ろにスライドする.
now_index = before_index + Bn
③ before_indexが交換範囲より後にあった場合 => 変化なし.
now_index = before_index
このパターンを基にシャッフルのたびにbefore_indexを求める感じで実装した.
問題B. 最高のコーヒー
問題へのリンク
=> いつかのエントリーで復習します。
問題C. ビット数
Largeには通用しても処理が終わらないようなアルゴリズム。
単純に全探索してみた.
#!/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 count_one(binary): length = len(binary) return len([char for char in binary if char == '1']) def ints(min, max): n = min while n < max: yield n n += 1 def calculate(N): if N ==1 : return 1 max = 0 for i in ints(1, N/2 +1): binary_one = format(i, 'b') binary_two = format(N-i, 'b') result = count_one(binary_one) + count_one(binary_two) if max < result: max = result return max if __name__ == '__main__': input_file = 'C-small.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] print "Case #%s: %s" %(i+1, calculate(N))
感想
Largeの提出の際に、「時間内なら再提出できます.」みたいなメッセージが出て、提出した回答が間違えていると勘違いしてしまってとても焦った。Largeの結果はコンテスト終了後に出るとのことだった。
このLargeの回答は一回だけしかできないand結果はコンテスト終了後というシステムはとても秀逸だと思う。また、参加者の提出したコードが見れるシステムも勉強になって素晴らしい。
結果的には、指定時間内で解けた問題は、6問中3問だった。点数的には54点中23点。
是非来年のCode Jam Japanとか本家のCode Jamもチャレンジしたい。そして自分の成長を感じられたらと思っている。
アリ本あたりを読んで戦闘力を上げる作戦を立てている。
とりあえず来週の決勝ラウンドでは上位200以内にもらえる限定Tシャツを目指して全力で挑みます。
"エラトステネスの篩"の書き方いろいろ - 比較
このエントリーは遥かに途中です。
概要
CodeJamJapan2011の練習問題Bで10^12までの素数求める必要があり、最初に書いたO(n^2)のアルゴリズムでは、とても計算が終わらなかったので、高速に素数を求めるためのアプローチとして有名なエラトステネスの篩という有名なアルゴリズムを知らなかったので調べたりやってみたことをエントリー。書き方でいろいろと実行時間がじ結局10^12の壁が乗り越えられなかったエントリー。
いろいろと書いてみた, ネットで調べてみた.
基本のアルゴリズム
def get_primes(N): n = 2 while n <= N: i = 2 while i < n: if n % i ==0: break i += 1 if i == n: yield n n += 1
再起でやるエラトステネスの篩
関数ints()は無限リストのジェネレーターを作るための関数.
def sieve(L): head = L.next() yield head for e in sieve(x for x in L if x % head != 0): yield e def ints(min, max): n = min while n < max: yield n n += 1
再起しないエラトステネス(自分で書いたやつ)
def my_sieve(N): L = ints(2, N+1) head = L.next() PL = [head, ] while(pow(head, 2) < N): L = iter([x for x in L if x % head != 0]) head = L.next() PL.append(head) return PL + list(L)
再起しないエラトステネス2, ネットで拾ってきたやつスクリプト
def eras(N): siv = range(N+1) siv[1] = 0 sqn = int(round(N**0.5)) for i in range(2, sqn+1): if siv[i] != 0: siv[2*i:N/i*i+1:i] = [0] * (N / i - 1) return filter(None,siv)
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の問題もコードをリファクタリングする話をしたはいいが、実はまだやってないので、そのエントリーにも終止符を打ちたい。今日この頃である。
コード改善のための参考予定のエントリー等
参加登録はここからできるみたいですよ
Code Jam Japan2011 練習問題B. 数の集合 (Small) 解いた
ざっくりと問題説明
連続した範囲[A,B]の整数に対して、素因数分解をして指定された値P以上の素数が共通している整数を同じ組にして、最終的に何組になりましたか？という問題。デフォルトの整数N個はそれぞれ自分しか所属していない集合に属している。(デフォルト集合はN個)
Pythonスクリプト
#!/usr/bin/env python # coding: utf-8 # vim: fileencoding=utf8 import sys import re import datetime def read_input_data(file_name): try: file_obj = file(file_name, 'r') length = int(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 def get_prime_factorization(num, prime_list): if num in prime_list: return [1, num] prime_factors = [1,] for prime in prime_list[1:]: while(True): if num % prime == 0: prime_factors.append(prime) num /= prime else: break if num == 1: break return prime_factors def get_prime(max_num): prime_list = [1,] for candidate in range(2, max_num+1): for j in range(2, candidate+1): if candidate == j: prime_list.append(candidate) break if candidate % j == 0: break if (candidate / 2) == j: prime_list.append(candidate) break return prime_list def get_num_duplicated(dup_set_list): join_flg = False for i in range(0, len(dup_set_list)): for j in range(i+1, len(dup_set_list)): if len(dup_set_list[i] & dup_set_list[j]) > 0: join_flg = True joined_set = dup_set_list[i] | dup_set_list[j] dup_set_list[i] = set() dup_set_list[j] = joined_set if join_flg: return get_num_duplicated([value for value in dup_set_list if len(value) > 0]) return sum(map(len, dup_set_list)) - len(dup_set_list) if __name__ == '__main__': start_time = datetime.datetime.now() input_file = './B-small-practice.in' #input_file = './B-large-practice.in' read_judge, length, dataset = read_input_data(input_file) if not read_judge: sys.exit() max_num = max([data[1] for data in dataset]) prime_list = get_prime(max_num) # for cache: 素因数分解した値を保存するため prime_factorization_list = {} for i in range(length): data_min = dataset[i][0] data_max = dataset[i][1] data_range = range(data_min,data_max+1) p = dataset[i][2] p_set = sorted(set(range(p, data_max+1)) & set(prime_list)) join_candidate = {} num_set = len(data_range) for num in data_range: # 素因数分解する. 既存のやつはcacheの prime_factorization_list を使用 try: prime_factorization_list[num] except KeyError: prime_factorization_list[num] = set(get_prime_factorization(num, prime_list)) # p以上の素因数を持つものを join_candidate に束ねる for p_prime in p_set: if p_prime in prime_factorization_list[num]: try: join_candidate[p_prime] except KeyError: join_candidate[p_prime] = [] finally: join_candidate[p_prime].append(num) # 2つ以上一致するものを選択 duplicated_list = [value for value in join_candidate.values() if len(value) > 1] answer = num_set - get_num_duplicated(map(set, duplicated_list)) print "Case #%s: %s" %(i+1, answer)
Largeに適用してみた。
そのままLargeの入力データを指定して実行してみると以下のエラー。
OverflowError: range() result has too many items
などと怒られた。さすがに12桁の数を普通に扱うには無理があった模様。
その問題は、以下のエントリーが解決してくれた。
Python: range and xrange for 13-digit numbers?
スクリプト変更後、実行できた！けど、レスポンスが返ってこない・・・。あれれー。おかしいぞ〜。
printを使ってどこで時間がかかっているか調べたら、初っ端の素数のリストを求めるところで詰んでいた。
いろいろ調べたところ、エラトステネスの篩というアルゴリズムが優秀らしい。その実装は次回にでも。
感想
久々に素数を求めるアルゴリズムを書くことになり、とっさにはパッと書くことができなかった。
また素数をいかに高速に求めるかというのはプログラミングコンテストになるくらいの課題だということに驚いた。
1000万個目の素数を超高速に出力せよ - Team-lablog
しかし、大きい数を扱うのはいろいろと大変だし、癖があることを勉強することができた。Cのコードもセグフォになっちゃうし・・・。JavaのBigIntegerクラスだと簡単にできそうだったが、せっかくだし、Pythonでこの問題を乗り越えたいな〜っと思ったので、近いうちにまたチャレンジする予定。
それにしてもCの実行速度の速さにはびっくりした。Cもちゃんと勉強したいな。いや〜プログラミング楽しいっすね。
素数求めるのに参考になりそうなサイト
参加登録がまだな人は登録しちゃいなよ！
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は解けないのだろうと感じた。でもキャッシュは強いことを確認できた。
参加登録がまだな人は登録しよう！
Code Jam Japan2011 練習問題A. 数珠繋ぎ (Small) 解いた
イメージ
ステップごとのイメージが文章を読んでるだけじゃ、わからなかったので、スライド作った。
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問くらいはやっておきたい。
参加登録がまだな人は登録しましょう！
初めて勉強会を開催してみて、感じたこと・収穫について。 第2回もやります！
概要
先週の木曜に、初めて勉強会(ATND: 第1回「集合知プログラミング」真面目に勉強する会 @池尻大橋)を主催して、
いろいろと気付いたことや収穫があったので、整理してみることに。
