唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

AtCoder Regular Contest 038 ooo- 1043->1183

競技プログラミング atcoder

32位 300点

ゴールデンウィークだったのでAtCoderに参加
C問題まで解けたのがよかったのか、めずらしくそこそこの順位がとれた
今回は2人ゲーム系の問題縛りでおもしろかった

公式の解説

www.slideshare.net

A: カードと兄妹 - AtCoder Regular Contest 038 | AtCoder

2人のプレイヤーが数字を書かれたカードを交互に取っていく
お互いに合計の数値を大きくしようとした時に、先攻のプレイヤーが得られる合計はいくつになるか

大きい順にソートして一つ飛ばしで取っていくだけ

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

def n():
    return int(raw_input())
def ln():
    return map(int, raw_input().strip().split())

n()
a = ln()
a.sort(reverse=True)

s = 0
for i in xrange(0, len(a), 2):
    s += a[i]

print s

B: マス目と駒 - AtCoder Regular Contest 038 | AtCoder

通行できるかどうかが定義された盤面が与えられる
一番左上の地点にコマを置いて、プレイヤーが交互に右か下か右下に動かしていって、動かせなかったプレイヤーの負けとなる
プレイヤーが勝利に向けて最適な戦略をとった時に先手と後手のどちらが勝つか答える

左や上に移動することはないので、右下から順に決めていくことができる
障害物があって移動できない場合、もしくは相手が勝つことが確定しているマスにしか移動できない場合に負けが確定する

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

def s():
    return raw_input().strip()
def ln():
    return map(int, raw_input().strip().split())

H, W = ln()
board = [[1] * (W + 2) for i in xrange(H + 2)]
for i in xrange(H):
    t = s()
    for j in xrange(W):
        if t[j] == '.':
            board[i + 1][j + 1] = 0

lose = [[0] * (W + 2) for i in xrange(H + 2)]

for i in xrange(H, 0, -1):
    for j in xrange(W, 0, -1):
        if lose[i + 1][j] == 0 or board[i + 1][j] == 1:
            if lose[i][j + 1] == 0 or board[i][j + 1] == 1:
                if lose[i + 1][j + 1] == 0 or board[i + 1][j + 1] == 1:
                    lose[i][j] = 1

print 'First' if lose[1][1] == 0 else 'Second'

C: 茶碗と豆 - AtCoder Regular Contest 038 | AtCoder

100点までしか取れなかった(最大は104点)

\(N\)個の茶碗が与えられる
それぞれの茶碗について、中に入っている豆の数と、手前の何個前までの範囲の茶碗に豆を移動できるかを与えられる
2人のプレイヤーが交互に豆を1つずつ移動していった時に、豆を移動できなかったプレイヤーが負けとなる

典型的なGrundy数の問題

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

def n():
    return int(raw_input())
def ln():
    return map(int, raw_input().strip().split())

N = n()

C = [0]
A = [0]
for i in xrange(N-1):
    c, a = ln()
    C.append(c)
    A.append(a)

grundy = [0] * (N)

for i in xrange(1, N):
    for j in xrange(max(i - C[i], 0), i):
        s.add(grundy[j])
    for k in xrange(N):
        if k not in s:
            grundy[i] = k
            break

result = 0
for i in xrange(N):
    for j in xrange(A[i] % 2):
        result ^= grundy[i]

print 'First' if result != 0 else 'Second'
'); jQuery.noConflict(true);