Google Code Jam Qualification Round 2013 A問題とC問題 (large 1)

• 問題

A問題のsmallとlarge、C問題のsmallとlarge 1を解きました。

Problem A. Tic-Tac-Toe-Tomek

4かける4のマス目がある。
各プレイヤーの駒(O, X)が縦横斜め一列に並んでいる場合にそのプレイヤーは勝利となる。
ただし一列のうち、ひとつの駒がTであっても勝利となる。
このゲームの勝敗を答える。
ただしどちらかの勝利以外に引き分けの場合と、ゲームが終わってない場合が考えられる。

やるだけ問題。

import sys

T = int(raw_input())
for i in xrange(1, T + 1):
    board = []
    for j in xrange(4):
        board.append(list(raw_input().strip()))
    empty = 0
    winX = False
    winO = False
    for j in xrange(4):
        countX = 0
        countO = 0
        countT = 0
        for k in xrange(4):
            if board[j][k] == '.':
                empty += 1
            elif board[j][k] == 'X':
                countX += 1
            elif board[j][k] == 'O':
                countO += 1
            elif board[j][k] == 'T':
                countT += 1
        if countX == 4 or (countX == 3 and countT == 1):
            winX = True
        elif countO == 4 or (countO == 3 and countT == 1):
            winO = True
    for k in xrange(4):
        countX = 0
        countO = 0
        countT = 0
        for j in xrange(4):
            if board[j][k] == '.':
                empty += 1
            elif board[j][k] == 'X':
                countX += 1
            elif board[j][k] == 'O':
                countO += 1
            elif board[j][k] == 'T':
                countT += 1
        if countX == 4 or (countX == 3 and countT == 1):
            winX = True
        elif countO == 4 or (countO == 3 and countT == 1):
            winO = True
    countX = 0
    countO = 0
    countT = 0
    for j in xrange(4):
        if board[j][j] == '.':
            empty += 1
        elif board[j][j] == 'X':
            countX += 1
        elif board[j][j] == 'O':
            countO += 1
        elif board[j][j] == 'T':
            countT += 1
    if countX == 4 or (countX == 3 and countT == 1):
        winX = True
    elif countO == 4 or (countO == 3 and countT == 1):
        winO = True
    countX = 0
    countO = 0
    countT = 0
    for j in xrange(4):
        if board[j][3 - j] == '.':
            empty += 1
        elif board[j][3 - j] == 'X':
            countX += 1
        elif board[j][3 - j] == 'O':
            countO += 1
        elif board[j][3 - j] == 'T':
            countT += 1
    if countX == 4 or (countX == 3 and countT == 1):
        winX = True
    elif countO == 4 or (countO == 3 and countT == 1):
        winO = True
    if winX:
        result = 'X won'
    elif winO:
        result = 'O won'
    elif empty == 0:
        result = 'Draw'
    else:
        result = 'Game has not completed'
    
    print "Case #{0}: {1}".format(i, result)
    raw_input()

Problem C. Fair and Square

与えられた範囲内の数について、以下の条件を満たす個数を答える。

• その数は回文数(12321などのようにひっくり返しても同じ数)である
• その数はある正の整数の二乗である。
• その数の平方根も回文数である

large 1では探索する数の範囲の最大値がである。
求めるべき数は二乗であるからまでの数の二乗を調べて、回文数になっていれば列挙しておけばいい。
(二乗する前の数も回文数なことを使えば更に調べる範囲を減らせる)
あとは列挙した条件を満たす数の中から、入力として与えられた範囲を二分探索して、その間の個数を返せばよい。
(条件を満たす数が少ないから、普通に線形探索しても通るかも)

import sys
import bisect

palindrome = []
valid = []
for i in xrange(1, 10**7 + 1):
    s = str(i)
    r = s[::-1]
    if s == r:
        palindrome.append(i)

for i in palindrome:
    square = i * i
    if square > 10 ** 14:
        break
    s = str(square)
    r = s[::-1]
    if s == r:
        valid.append(square)

T = int(raw_input())
for i in xrange(1, T + 1):
    A, B = map(int, raw_input().split())
    start = bisect.bisect_left(valid, A)
    end = bisect.bisect_right(valid, B)
    print "Case #{0}: {1}".format(i, end - start)