唯物是真 @Scaled_Wurm

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

AtCoder Beginner Contest 023 oo△△

競技プログラミング atcoder

微妙に競技プログラミングやる気が上がっているので参加

65位 260点

公式の解説

www.slideshare.net

A: 加算王 - AtCoder Beginner Contest 023 | AtCoder

数字の各桁の値の総和を求める

print sum(map(int, str(input())))

B: 手芸王 - AtCoder Beginner Contest 023 | AtCoder

あるルールにもとづいて作成された文字列かどうかを調べる

長さごとに文字は一意に決まるので、生成してみて比較した

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

def s():
    return raw_input().strip()
def n():
    return int(raw_input())

N = n()
S = s()

T = N / 2

t = 'b'
pos = 0
for i in xrange(1, T + 1):
    if i % 3 == 1:
        t = 'a' + t + 'c'
    if i % 3 == 2:
        t = 'c' + t + 'a'
    if i % 3 == 0:
        t = 'b' + t + 'b'

if S == t:
    print T
else:
    print -1

C: 収集王 - AtCoder Beginner Contest 023 | AtCoder

行列のうちの行と列の位置が複数与えられる
与えられた箇所は\(1\)その他は\(0\)の行列を考える
ある行とある列の数値の総和が\(K\)になる組み合わせ数を答える(ただし\(i\)行と\(j\)列を選んだ時に、\(i\)行と\(j\)列の要素を足すのは一度だけ)

行と列の総和を求めて、合計が\(K\)になる組み合わせ数の総和を求めてから、要素が\(1\)の箇所を2回数えている場合の補正をする(\(i\)行と\(j\)列の要素が\(1\)の場合代わりに合計が\(K+1\)の組み合わせ数を求めないといけない)

本番では行列中の要素が\(1\)の箇所だけ見れば結果を修正できることに気づかなかった
部分点しか取れなかったソースコード

# -*- 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())

R, C, K = ln()
N = n()
row = collections.Counter()
col = collections.Counter()
pos = collections.Counter()
for i in xrange(N):
    r, c = ln()
    row[r] += 1
    col[c] += 1
    pos[(r, c)] += 1

count = 0

cols = []
for c in xrange(1, C + 1):
    cols.append((col[c], c))

cols.sort()


for r in xrange(1, R + 1):
    idx = bisect.bisect_left(cols, K - row[r])
    if idx == -1:
        continue
    for i in xrange(idx, C):
        c = cols[i][1]
        if cols[i][0] > K + 1:
            break
        if row[r] + col[c] - pos[(r, c)] == K:
            count += 1

print count

D: 射撃王 - AtCoder Beginner Contest 023 | AtCoder

風船の高さと上昇速度が与えられる
1秒毎に風船を1つ割ることができるとき、最大の高さになった風船の高さを最小化したい

二分探索で解ける
本番ではPythonで普通に書いてTLEになったが、Pythonでもがんばれば解けるらしい

TLEで部分点のコード

# -*- 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()
HS = []
for i in xrange(N):
    HS.append(ln())

lb = 1
ub = 1e16
L = len(HS)
while ub - lb > 1:
    mid = int((ub + lb) / 2)
    temp = []
    for h, s in HS:
        u = ((mid - h) / s) + 1
        temp.append((u, h, s))
    temp.sort(reverse=True)
    for i, (u, h, s) in enumerate(temp):
        if L - i > u:
            break
    else:
        ub = mid
        continue
    lb = mid

print ub