Google Code Jam 2013 - Qualification Round

プログラミング・プロコン

先日GCJの予選ラウンドが開催されました。昨年に引き続きPythonの練習のために参加しました。が普段全然使わないのでほぼ完全に文法とか忘れてましたが（爆）。彼女が遊びに来ていて旅行とかしてたので実は疲れてやる気なかったんですが、なんか「Cだけ完答すれば予選通過するよ」とかいう噂を聞いて、Cだけやるつもりが結局それ以外もやってしまいました。結果はABC完答（Dはやってない）で順位は644位でした。

挑戦した順に簡単に解説書きます。

C. Fair and Square

いろいろな解き方があって良問でしたね。もち最初からLarge2狙いで。入力の凄まじい大きさ（10^100）を見て、これは解析的に解く方法があるんだなと予想。とりあえず処理時間を無駄なく済ますために、まず最初に必要な「Fair&Square数」を全部列挙する関数を呼んで、それを二分探索で範囲絞ることでカウントすることに。
ではどうやって「Fair&Square数」を列挙するか？。ポイントは筆算を各桁変数にして書いてみるとわかりやすい。例えば３ケタの回文数 ABA の二乗は、全ての桁で繰り上がりがなければ（繰り上がりがあると対称性が崩れる）それ自体が回文となることが分かる。またちょうど真ん中の桁のところが A^2+B^2+A^2 になる。最も繰り上がりに弱いのはその真ん中の桁。ここは感覚的だけど、項数がどの桁よりも多くかつ定義もL2ノルムと同等なのできっとそうだろうと予想。なので A^2+B^2+A^2 < 10 みたいな条件を満たす数字をカウントすればよろし。
全数試すのは多すぎてアウトなので、各桁を深さ優先してくことでカウントした。条件を満たすのは（一桁の3の場合を除き）各桁は0,1,2しかありえないので、それらを順番に試せばよい。暫定二乗和が10を超えたなら繰り上がり発生を意味するので打ち切り。複数の桁に2を含むケースはほとんど刈れるので、これで大雑把に考えても 2^(100/4) =3400万パターン程度には絞れる形に。Python（非PyPy）でもLarge2が2秒程度で済む。

import sys
import bisect

D = int(100/2)
fsnums = []

def search_fixed_digits(d,k=0,cap=9,num=0):
	if cap<0: return
	if d<=2*k:
		fsnums.append(num*num)
		return
	for n in range(1 if k==0 else 0,3): #only 0,1,2 can satisfy the condition
		num2,cap2 = num,cap
		if 2*k==d-1: #d-th digit locates the exact center
			num2 += (10**k)*n
			cap2 -= n*n
		else:
			num2 += (10**k+10**(d-1-k))*n
			cap2 -= n*n*2
		search_fixed_digits(d,k+1,cap2,num2)
	return

def find_fair_square_numbers():
	#store the answers of numbers with 1-digit in advance
	fsnums.append(1*1)
	fsnums.append(2*2)
	fsnums.append(3*3)
	#search numbers with d-digits
	for d in range(2,D+1):
		search_fixed_digits(d)
	return

if __name__ == '__main__':
	find_fair_square_numbers()
	T = int(input())
	for t in range(T):
		a,b = [int(i) for i in sys.stdin.readline().split()]
		ans = bisect.bisect_right(fsnums,b)-bisect.bisect_left(fsnums,a)
		print('Case #{}: {}'.format(t+1,ans))

A. Tic-Tac-Toe-Tomek

盤面の状況（勝敗or引き分けorゲーム途中）を判定すればいいだけ。タテ・ヨコ・ナナメにそれぞれのプレイヤーが４連になってるかどうか判定する。もしどちらもなってない場合、空きスペースがあればゲーム途中、なければドロー状態。ってな具合。盤面サイズも 4x4 なので愚直にループ回すだけでＯＫ。

import sys

N = 4

def is_win(board,side):
	#horizontal check
	for j in range(N):
		flag = True
		for i in range(N):
			if board[j][i]!=side and board[j][i]!='T':
				flag = False
		if flag==True:
			return True
	#vertical check
	for i in range(N):
		flag = True
		for j in range(N):
			if board[j][i]!=side and board[j][i]!='T':
				flag = False
		if flag==True:
			return True
	#diagonal check
	flag = True
	for i in range(N):
		if board[i][i]!=side and board[i][i]!='T':
			flag = False
	if flag==True:
		return True
	flag = True
	for i in range(N):
		if board[N-1-i][i]!=side and board[N-1-i][i]!='T':
			flag = False
	if flag==True:
		return True
	return False

def has_empty(board):
	for j in range(N):
		for i in range(N):
			if board[j][i]=='.':
				return True
	return False

if __name__ == '__main__':
	T = int(input())
	for t in range(T):
		board=[]
		for i in range(N):
			board.append(input())
		
		ans = 'Draw'
		if is_win(board,'X'):
			ans = 'X won'
		elif is_win(board,'O'):
			ans = 'O won'
		elif has_empty(board):
			ans = 'Game has not completed'
		print('Case #{}: {}'.format(t+1,ans))
		if t+1<T:
			input()

B. Lawnmower

十分通過ライン超えたのでやる気が出ず。楽そうな実装が見つかればやろうかなー、と思ってたら見つけたので寝ずに実装した。
タテ・ヨコを貫く形でしか刈れないので、２面の側面図を想像してみると良い。所望のデザインからその側面図を考えて、逆にその側面図通りに刈ってみる。できたものが所望のデザインと等しければデキる、そうでなければデキない。

import sys

def is_possible(board,N,M):
	highestN = [-1]*N
	highestM = [-1]*M
	for n in range(N):
		for m in range(M):
			highestN[n] = max(highestN[n],board[n][m])
			highestM[m] = max(highestM[m],board[n][m])
	
	for n in range(N):
		for m in range(M):
			model = min(highestN[n],highestM[m])
			if board[n][m]!=model:
				return False
	return True

if __name__ == '__main__':
	T = int(input())
	for t in range(T):
		N,M = [int(i) for i in sys.stdin.readline().split()]
		board=[]
		for i in range(N):
			board.append([int(i) for i in sys.stdin.readline().split()])
		
		ans = 'YES' if is_possible(board,N,M) else 'NO'
		print('Case #{}: {}'.format(t+1,ans))

D. Treasure

B'zか！と思うくらいには年喰ってます。問題読んでLargeは解けそうになかったのでやってません。Smallはメモイズ探索あたりでイケる感じでしたが、朝４時近くて眠かったので寝ました。

むすび

今回のC問題みたいに、最近のGCJはこういうとてつもなく大きい整数を扱う問題が頻出なので、Pythonみたいにそのままの整数型で対応できる言語を選んだほうが楽ですね。昔C++使ってた頃はアンフェアだ！とか思ってた（笑）けど、Google的には問題に合わせて言語を選ぶセンスも問いたいんでしょう、たぶん。
最初からLarge狙いで考えてて、自分の力で解ける範囲はちゃんとしっかり解けたかな〜という印象です。どのコードも短く無駄なく書けて満足。でも俺よりできる方々が全力で参加してないので、今後この順位をキープするのは無理そう（笑）。あとPythonだとどうしてもいろいろ調べながら実装しないといけないので、コーディング速度が遅いですね。まぁ、Pythonのリハビリとして参加してるので別にいいんですけど。次のラウンドが自分にとって山場ですね。