唯物是真 @Scaled_Wurm

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

AtCoder Regular Contest #014 ooox

競技プログラミング atcoder

82位。いつの間にか2級になっていた

A: 君が望むなら世界中全てのたこ焼きを赤と青に染め上げよう - AtCoder Regular Contest #014 | AtCoder

数値が偶数ならBLUE、奇数ならREDと出力すればいいだけ

# -*- coding: utf-8 -*-
import sys
import collections

N = int(raw_input())

color = ['Blue', 'Red']

print color[N % 2]

B: あの日したしりとりの結果を僕達はまだ知らない。 - AtCoder Regular Contest #014 | AtCoder

しりとりの勝敗を判定すればよい。
同じ言葉を二回以上言ってはダメなので、言葉の重複と、語尾と次の語頭が一致しているかをチェック

# -*- coding: utf-8 -*-
import math
import sys
import datetime

N = int(raw_input())

check = set()

result = ['LOSE', 'WIN']

before = ''
for i in xrange(N):
    line = raw_input()
    if line in check:
        print result[i % 2]
        break
    check.add(line)
    if i > 0 and before[-1] != line[0]:
        print result[i % 2]
        break
    before = line
else:
    print 'DRAW'

C: 魂の還る場所 - AtCoder Regular Contest #014 | AtCoder

3色のボールを決められた順番で筒に入れていく。
ただし筒は左右どちらから入れてもよく、同じ色のボールが2つくっついた場合消滅する。
残るボールの最小の長さを答える

各色ごとにボールの数の偶奇をとって足しあわせればいいらしいです。
私はビームサーチで無理矢理通しました

# -*- coding: utf-8 -*-
import math
import sys
import collections

deq = collections.deque()

N = int(raw_input())

ball = raw_input()

candidate = [(0, deq)]

for b in ball:
    new_candidate = []
    for n, d in candidate:
        L = len(d)
        if L == 0:
            d.append(b)
        else:
            head = d[0]
            tail = d[-1]
            if head == b:
                d.popleft()
            elif tail == b:
                d.pop()
            elif L == 1:
                d.append(b)
            else:
                d2 = collections.deque(d)
                d.append(b)
                d2.appendleft(b)
                new_candidate.append((len(d2), d2))
        new_candidate.append((len(d), d))
    new_candidate.sort()
    candidate = new_candidate[:10000]

print candidate[0][0]

D: grepマスター - AtCoder Regular Contest #014 | AtCoder

いくつかの行番号とその前x行と後ろy行という範囲の情報が与えられた時に、カバーする行数を答える
ただし行番号はN個、xとyのペアはM個与えられる
各xyのペアごとに、N個の行番号の前後すべての合計を答える

O(NM)のアルゴリズムはできたんですが、O(10^10)なので当然時間切れ(TLE)。

Twitterを見ていると、行同士の間隔をソートしてから二分探索すれば効率的に計算できるみたいです

ライター解を見つけたので追加 以下はTLEしたコード
# -*- coding: utf-8 -*-
import math
import sys
import collections


all, N, M = map(int, raw_input().split())

L = []
for i in xrange(N):
    L.append(int(raw_input()))

xy = []
for i in xrange(M):
    xy.append(map(int, raw_input().split()))

diff = []

for i in xrange(N - 1):
    diff.append(L[i + 1] - L[i])

for A, B in xy:
    count = 0
    start = L[0]
    end = L[0]

    for i in xrange(N - 1):
        if diff[i] <= A + B:
            end = L[i + 1]
        else:
            count += min(end + B, all) - max(1, start - A) + 1
            start = L[i + 1]
            end = L[i + 1]
    count += min(end + B, all) - max(1, start - A) + 1

    print count