Codeforces Round #167 (Div. 2) ooo-- 1532->1665

Dashboard - Codeforces Round #167 (Div. 2) - Codeforces

実はC問題が解けたのは初めて

Problem - A - Codeforces

与えられた数に1から5のいずれかの数を足したときに、人数で割った余りが1になる場合の数を求める。

import sys

n = int(raw_input())

hand = map(int, raw_input().split())
s = sum(hand) - 1

result = 0
for i in xrange(1, 6):
    if (s + i) % (n + 1) != 0:
        result += 1
print result

Problem - B - Codeforces

与えられた数のうちビットが1になっている数の等しい組の個数を答える。

ビットカウントだと理解できずに、問題に書かれていた再帰関数を愚直に実装してメモ化して解いた↓

import sys
import collections

memo = {}

def f(n):
    if n == 0:
        return 0
    elif n in memo:
        return memo[n]
    elif n % 2 == 0:
        v = f(n / 2)
        memo[n] = v
        return v
    elif n % 2 == 1:
        v = f((n - 1) / 2) + 1
        memo[n] = v
        return v

n = int(raw_input())
arr = map(int, sys.stdin.readline().split())

count = collections.Counter()

for a in arr:
    count[f(a)] += 1

result = 0
for key, v in count.iteritems():
    if v > 1:
        result += v * (v - 1)

print result / 2

Problem - C - Codeforces

手前から階段にブロックを落として行く時に、各々のブロックの底面がどの高さになるかを答える。

ステージの配列の高さを更新していくと、 $O(nm)$ なのでTLEになってしまう。
必ず手前から落としていくので、一番手前とブロックの奥側の端のどちらか高いほうが底面になる。
故に一番手前の高さだけを更新していけば $O(m)$ で計算できる

import sys

memo = {}


n = int(raw_input())
stair = map(int, sys.stdin.readline().split())

m = int(raw_input())
block = []
for i in xrange(m):
    block.append(map(int, sys.stdin.readline().split()))

cur_h = stair[0]
result = []
for b in block:
    temp_h = max(cur_h, stair[b[0] - 1])
    result.append(temp_h)
    cur_h = temp_h + b[1]

for r in result:
    print r