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

唯物是真 @Scaled_Wurm

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

Codeforces Round #169 (Div. 2) oooo- 1588->1710

codeforces 競技プログラミング

Div. 1に上がれたので今年の目標を一つ達成。
次回落ちないといいなぁ((((;゚Д゚))))

71位っていう二桁順位をとったのにギリギリDiv. 1までしか上がれないんですね……。

Problem - A - Codeforces

問題文のとおりにやるだけ。

n, k = map(int, raw_input().split())

m = -10**10
for i in xrange(n):
    f, t = map(int, raw_input().split())
    if t > k:
        m = max(m, f - (t - k))
    else:
        m = max(m, f)
print m

Problem - B - Codeforces

奇数個ある文字の種類数を数えて2で割った余りで場合分け。
単純にシミュレーションしても間に合う。

import sys
import collections

line = sys.stdin.readline().strip()

count = collections.Counter()
for c in line:
    count[c] += 1

odd = 0
even = 0
for c in count:
    if count[c] % 2 == 1:
        odd += 1
    else:
        even += 1

isFirst = True

while odd > 1:
    if even > 0:
        even -= 1
        odd += 1
    else:
        odd -= 1
    isFirst = not isFirst
if isFirst:
    print 'First'
else:
    print 'Second'

Problem - C - Codeforces

要素が使われる回数を求めて、多い順に大きな整数との積を計算して足していく。
要素が使われる回数を求める際にはいわゆるいもす法を用いた。

import sys

n, q = map(int, sys.stdin.readline().split())
seq = map(int, sys.stdin.readline().split())

seq.sort(reverse=True)
temp = [0 for i in xrange(n + 2)]

seq.sort(reverse=True)
for i in xrange(q):
    start, end = map(int, sys.stdin.readline().split())
    temp[start] += 1
    temp[end + 1] -= 1


for i in xrange(1, n + 2):
    temp[i] += temp[i - 1]
temp.sort(reverse=True)

i = 0
result = 0

while temp[i] > 0:
    result += seq[i] * temp[i]
    i += 1

print result

Problem - D - Codeforces

XORが1になる最上位のビットを求めて、そこから1桁目まで全部1のときの数値を返せばいい。

import sys

l, r = map(int, sys.stdin.readline().split())

small = bin(l)[2:]
big = bin(r)[2:]

L = len(big)
small = small.zfill(L)

for i in xrange(L):
    if small[i] != big[i]:
        print int('1' * (L - i), 2)
        break
else:
    print 0
"""
-->