自分を操る超集中力/メンタリストDaiGo

 今月初頭にキャンパス内の図書館主催の選書ツアーに参加してきました。参加者が少なかったおかげで20冊近くの本を選ぶことができて大満足でした。そこで購入した本を最近必死に読み進めています。

今日読み終わったのは↓の本。

自分を操る超集中力

自分を操る超集中力

 

 一時期テレビにたくさん出ていたメンタリストのDaiGoが送る「集中力」について本です。昔から集中力に波があるタイプで、仕事で効率よく成果を上げるためにもなんとかせねばと思っていたのと、DaiGoに限らずメンタリズムのパフォーマンスが個人的に好きだったので、手に取りました。

本書曰く、集中力は自分自身で鍛錬・起動・回復など制御できるものだそうです。本の意図としては、まず集中力とはなにかを正しく把握し、それを制御する方法を理解し、さらに実践できるようになろう、ということだと思います。本の序盤にでてきますが、集中力を生み出す「ウィルパワー」というのは有限であるため、その「総量の増やし方」「消費量の節約の仕方」「回復の仕方」に焦点があてられています。

個人的に一番刺さったのは、「多すぎる選択がウィルパワーを消耗させてしまう」という点でしょうか。なので、どのように選択肢を減らしていくのか、時間・場所・食事など様々な観点からそのノウハウが語られています。中には一般的な社会人には実践不可能ではないかと思われるものもありますが、知っておくだけでもずいぶん気持ちや考え方に変化が生まれました。そのうち気に入ったものをいくつか実践するだけでも効果が上がるように思いました。

僕も、いきなり全ては負荷が大きい(というか無理な)ので、現状で手軽にはじめられる方法をいくつか試しているのですが、明らかに生産性が上がってます(笑)。まぁ今まではヒドすぎたというだけかもしれませんが(汗)。この調子で成果が上がればいいな。。

DaiGoらしく理路整然とまとまっており文章量も少ないので、とても読みやすかったです。オススメ!

Google Code Jam 2013 - Qualification Round

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

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

C. Fair and Square

いろいろな解き方があって良問でしたね。もち最初からLarge2狙いで。入力の凄まじい大きさ(10^100)を見て、これは解析的に解く方法があるんだなと予想。とりあえず処理時間を無駄なく済ますために、まず最初に必要な「Fair&Square数」を全部列挙する関数を呼んで、それを二分探索で範囲絞ることでカウントすることに。
ではどうやって「Fair&Square数」を列挙するか?。ポイントは筆算を各桁変数にして書いてみるとわかりやすい。例えば3ケタの回文数 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ゲーム途中)を判定すればいいだけ。タテ・ヨコ・ナナメにそれぞれのプレイヤーが4連になってるかどうか判定する。もしどちらもなってない場合、空きスペースがあればゲーム途中、なければドロー状態。ってな具合。盤面サイズも 4x4 なので愚直にループ回すだけでOK。

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

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

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はメモイズ探索あたりでイケる感じでしたが、朝4時近くて眠かったので寝ました。

むすび

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

OpenCV2.4による顕著性マップの実装

[2013/07/17追記] 論文中のアルゴリズム再現性についていくつか御指摘&コメントを頂きました。特にコードには反映させていませんが、注意点を★コメントの形で加えました。運用する際はあらかじめ注意点を把握したうえで運用ください。
顕著性マップというのは、ある画像における人間の視覚的な注目度を表したマップのことで、コンピュータービジョン分野の多くの研究で活用されている重要なテーマです。一例として下の画像を見てください。

続きを読む

画素あたり定数時間ガウシアンフィルタのサーベイ

@君が主催する『Computer Vision Advent Calendar 2012』に自分も微力ながら参戦することにしました。テーマはCV分野でもよく用いられている『ガウシアンフィルタ』についてです。特に処理時間がスケールσに依存しない『(画素あたり)定数時間ガウシアンフィルタ』についてまとめます。これはスケールスペースを活用する手法(SIFT特徴点検出や顕著性マップなど)において役立つかと思われます。私はこのテーマについてここ一年取り組んできたのですが、その中でつかんだコツや実装後の感想などについて主観的にですが列挙してみます。参考文献も挙げますので、興味のある方はぜひトライしてみてください。
ちなみに画像処理では2次元フィルタリングについて考える必要がありますが、ガウシアンフィルタは可分(separable)である(N次元ガウシアンはN個の1次元ガウシアンの積に分解できる)ため、特に言及がない場合は1次元を前提に話をしていますのでご注意ください。

続きを読む

ガウシアンフィルタの並列処理実装の性能比較(ループアンロール)

こんにてぃーは。前回の続きです。今回は、大カーネルのときにSSE並列のコードが遅くなる原因について検証し、その改善を図ります。

続きを読む