roiti46's blog

主に競プロ問題の解説を載せてます

Google Code Jam 2015 Qualification Round: D. Ominous Omino

条件を少し間違えてしまい、Largeは落ちてしまった。

問題はこちら

問題

X-ominoとはX個の正方形タイルをつなげてできる図形のことを指す。RICHARDとGABRIELはこれを使ったあるゲームをしている。ゲームは以下のように進んでいく。

  1. まずXと盤面の大きさRxCを決める。
  2. RICHARDはX-ominoesの中から1つの図形を選択する。
  3. 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のときの条件を間違えていた。

きちんと計算する解法は他の方の解法を参照してください。。。