Google Code Jam 2015 Qualification Round: D. Ominous Omino
条件を少し間違えてしまい、Largeは落ちてしまった。
問題はこちら。
問題
X-ominoとはX個の正方形タイルをつなげてできる図形のことを指す。RICHARDとGABRIELはこれを使ったあるゲームをしている。ゲームは以下のように進んでいく。
- まずXと盤面の大きさRxCを決める。
- RICHARDはX-ominoesの中から1つの図形を選択する。
- GABRIELはRICHARDが選択した図形を少なくとも1つ使い、盤面をX-ominoesで埋めていく。
盤面をX-ominoesで埋めるとは、それぞれの図形が重なりなく、盤面からはみ出ることもなく、すべてのマス上にタイルが存在するという事である。GABRIELが盤面を埋めることができればGABRIELの勝ち、そうでなければRICHARDの勝ちとする。RICHARDが必勝となるような図形の選び方があるかどうかを与えられたX,R,Cごとに答えよ。
解法
X ≧ 7 のときはRICHARDが必勝である。問題の7-ominoesの図を見ればわかるが、X ≧ 7 ならば穴の開いた図形を作ることができる。RICHARDがそういった図形を選べばGABRIELが盤面を埋めることは決してできない。
また R*C が X で割り切れないときもRICHARDの勝ちである。それ以外ではRとCごとに場合分けをすればいい。頑張れば手で解ける問題。
- X が1または2のとき:この時は必ず盤面を埋められる。
- X が3のとき:min(R,C) > 1 なら、どの図形を選ばれても盤面を埋められる。
- Xが4のとき:min(R,C) > 2 なら、どの図形を選ばれても盤面を埋められる。
- Xが5のとき:min(R,C) > 2 かつ (R,C) != (5,3 or 3,5) なら、盤面を埋められる。
- Xが6のとき:min(R,C) > 3 なら、どの図形を選ばれても盤面を埋められる。
T = int(raw_input()) for loop in xrange(T): X, R, C = map(int, raw_input().split()) R,C = sorted([R,C]) if X >= 7 or R*C%X > 0: winner = 0 elif X == 1 or X == 2: winner = 1 elif X == 3: if min(R,C) == 1: winner = 0 else: winner = 1 elif X == 4: if min(R,C) <= 2: winner = 0 else: winner = 1 elif X == 5: if min(R,C) <= 2 or [R,C] == [3,5]: winner = 0 else: winner = 1 elif X == 6: if min(R,C) <= 3: winner = 0 else: winner = 1 print "Case #%d: %s"%(loop+1, ["RICHARD","GABRIEL"][winner])
まとめ
本番ではXが6のときの条件を間違えていた。
きちんと計算する解法は他の方の解法を参照してください。。。