自分を操る超集中力／メンタリストDaiGo
今月初頭にキャンパス内の図書館主催の選書ツアーに参加してきました。参加者が少なかったおかげで２０冊近くの本を選ぶことができて大満足でした。そこで購入した本を最近必死に読み進めています。
今日読み終わったのは↓の本。
一時期テレビにたくさん出ていたメンタリストのDaiGoが送る「集中力」について本です。昔から集中力に波があるタイプで、仕事で効率よく成果を上げるためにもなんとかせねばと思っていたのと、DaiGoに限らずメンタリズムのパフォーマンスが個人的に好きだったので、手に取りました。
本書曰く、集中力は自分自身で鍛錬・起動・回復など制御できるものだそうです。本の意図としては、まず集中力とはなにかを正しく把握し、それを制御する方法を理解し、さらに実践できるようになろう、ということだと思います。本の序盤にでてきますが、集中力を生み出す「ウィルパワー」というのは有限であるため、その「総量の増やし方」「消費量の節約の仕方」「回復の仕方」に焦点があてられています。
個人的に一番刺さったのは、「多すぎる選択がウィルパワーを消耗させてしまう」という点でしょうか。なので、どのように選択肢を減らしていくのか、時間・場所・食事など様々な観点からそのノウハウが語られています。中には一般的な社会人には実践不可能ではないかと思われるものもありますが、知っておくだけでもずいぶん気持ちや考え方に変化が生まれました。そのうち気に入ったものをいくつか実践するだけでも効果が上がるように思いました。
僕も、いきなり全ては負荷が大きい（というか無理な）ので、現状で手軽にはじめられる方法をいくつか試しているのですが、明らかに生産性が上がってます(笑)。まぁ今まではヒドすぎたというだけかもしれませんが(汗)。この調子で成果が上がればいいな。。
DaiGoらしく理路整然とまとまっており文章量も少ないので、とても読みやすかったです。オススメ！
ハミング距離の計算はホントに速いのか？
これは@sakanazensen君が主催する『Computer Vision Advent Calendar 2013』の12/8の記事です。今年はあまり活発でないようなので、小ネタですが参戦しました。
続きを読む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のリハビリとして参加してるので別にいいんですけど。次のラウンドが自分にとって山場ですね。
画素あたり定数時間ガウシアンフィルタのサーベイ
@sakanazensen君が主催する『Computer Vision Advent Calendar 2012』に自分も微力ながら参戦することにしました。テーマはCV分野でもよく用いられている『ガウシアンフィルタ』についてです。特に処理時間がスケールσに依存しない『（画素あたり）定数時間ガウシアンフィルタ』についてまとめます。これはスケールスペースを活用する手法（SIFT特徴点検出や顕著性マップなど）において役立つかと思われます。私はこのテーマについてここ一年取り組んできたのですが、その中でつかんだコツや実装後の感想などについて主観的にですが列挙してみます。参考文献も挙げますので、興味のある方はぜひトライしてみてください。
ちなみに画像処理では2次元フィルタリングについて考える必要がありますが、ガウシアンフィルタは可分(separable)である（N次元ガウシアンはN個の1次元ガウシアンの積に分解できる）ため、特に言及がない場合は1次元を前提に話をしていますのでご注意ください。
