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シャツを目指して全力で挑みます。
