AtCoder ABC 121の反省

Python

AtCoder Beginner Contest 121 - AtCoderやったのでまたメモっておく。

A - White Cells

特に悩むことはない。白色のマス目を長方形に並べてカウントすれば良い。

# coding: utf-8

H, W = [int(i) for i in input().split()]
h, w = [int(i) for i in input().split()]

print((H - h) * (W - w))

B - Can you solve this?

特に考える部分は無かった。まずは最初の回答。

# coding: utf-8

N, M, C = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

correct = 0

for i in range(N):
    A = [int(i) for i in input().split()]
    if sum(i * j for i, j in zip(A, B)) + C > 0:
        collect += 1

print(correct)

ちょっと整理して内包表記で書き直してみたけど別に早くならず可読性だけ落ちてうーん…という感じ。

# coding: utf-8

def read_ints():
    return [int(i) for i in input().split()]

N, M, C = read_ints()
B = read_ints()

correct = sum(
    sum(i * j for i, j in zip(read_ints(), B)) + C > 0 
    for k in range(N)
    )

print(correct)

C - Energy Drink Collector

最初小細工しようとして時間超過してしまったので結局bruteforceっぽい感じで解いてしまった、ソートの速度次第では…と思ってたけど解説読んでも同じこと書いてあったのでこれで良しとする。

件数が多かったのでデータの読み込み方を少し調べた。sys.stdin.readlineを使うと早くなるらしい（cf. Pythonの知っておくと良い細かい処理速度の違い8個 - kumilog.net）。

# coding: utf-8
import sys
input = sys.stdin.readline
 
N, M = [int(i) for i in input().split()]
 
plices = [[int(i) for i in input().split()] for _ in range(N)]
 
plices.sort(key = lambda x:x[0])
 
m = 0
cost = 0
 
for i in range(N):
    if m >= M:
        break
    buy = min(M - m, plices[i][1])
    cost += plices[i][0] * buy
    m += buy
 
print(cost)

D - XOR World

締切に間に合わなかったが、筋は悪くないと思って考え続けた結果終了40分後に解けた。

0〜その数字までを対象に、ある桁に1が何回出現するのか、という点を考えて解いた。スピードは足りてたけど正直汚い。

# coding: utf-8

A, B = [int(i) for i in input().split()]

def count_1(bi, idx):
    bi = bi[::-1]
    cnt = 0
    if idx > 0:
        for i in range(0, idx):
            cnt += int(bi[idx]) * int(bi[i]) * int(2**i)
    if idx < (len(bi) - 1):
        for i in range(idx + 1, len(bi)):
            cnt += int(bi[i]) * int(2**i) / 2
    cnt += int(bi[idx])        
    return(int(cnt))

a = str(bin(max(A-1, 0)))[2:]
b = str(bin(B))[2:]
a = (len(b) - len(a)) * "0" + a # 長さ調整

def count_1s(bi):
    return([count_1(bi, i) for i in range(len(bi))[::-1]])

a_cnt = count_1s(a)
b_cnt = count_1s(b)


print(int("".join([str((i - j) % 2) for i, j in zip(b_cnt, a_cnt)]), 2))

で、解説を見て書き直した。

# coding: utf-8

def F_0n(n): # F(0, n)を求める
    if n % 2 == 0:
        return (n // 2 % 2) ^ n
    else:
        return (n + 1) // 2 % 2

def F(a, b):
    return F_0n(a - 1) ^ F_0n(b)

A, B = [int(i) for i in input().split()]

print(F(A, B))

きちんと排他的論理和の性質から攻めていくべきだった。半端に書き下して半端に法則を見つけてしまい、それをそのままコードにしようとしてしまったのが敗因な気がする。