読者です 読者をやめる 読者になる 読者になる

GCJ 2013の途中まで

リアルタイムで参加し損ねたので、ちまちま暇なときに解いています。いまはProblemCに取り組んでいて、Smallは通るが、Largeだと遅くて答えが出せない・・・。
Bまでは解けたので、備忘録代わりに。

https://code.google.com/codejam/contest/2270488/dashboard

Problem A. Tic-Tac-Toe-Tomek

雑な問題の要約

二人のプレイヤー(X、O)が、4x4のマスにそれぞれXとOを埋めていく。縦・横・ななめのいずれかの方向にXが4つあるいはOが4つ揃った時、勝敗が決まる。ワイルドカードとしてTが置かれる時もある。
盤面の状況を入力として、Xが勝ち、Oが勝ち、引き分け、ゲームが終わっていない、の4状態を判定せよ。

方針

これは何も考えずに、縦、横、斜めでXかOが揃っているか総当り的に確認すればOK。

Problem B. Lawnmower

雑な問題の要約

庭にX(m)*Y(m)長方形で高さ100mmの芝生がある。芝刈り機は、芝生の端からしか入ることができず、各辺に対して直角に、1m単位で真っ直ぐ進む。逆の端に着くまで止めることはできない。この芝刈り機は端から切り始める時に、芝生を何mmに刈り揃えるかを決める必要がある。
芝生の高さの設計図を入力として、設計通りに芝生を刈り取れるかどうか判定せよ

方針

ある場所からスタートして、逆端に辿り着くまではある長さでしか刈り取れない、ということは、ある場所の芝生の長さに対して、「その上下方向と左右方向により長い芝生が存在する場合」には、その形状に刈り取ることが不可能となる。(芝生を短くする設定で芝刈り機をスタートさせると、長く保たなければならない部分も短くされてしまう。)

サンプルコード

def solve(field):
    isNg = False

    for i in range(len(field)):
        for j in range(len(field[i])):
            vertNg = False
            horiNg = False

            val = field[i][j]
            # 縦横、自分より高いものがあるか調べる
            for k in range(len(field)):
                if k == i:
                    continue
                
                if field[k][j] > val:
                    vertNg = True

            for k in range(len(field[i])):
                if k == j:
                    continue
                if field[i][k] > val:
                    horiNg = True

            if horiNg and vertNg:
                isNg = True
                break

        if isNg:
            break

    return isNg


ProblemC以降もがんばろう。