AtCoder Beginner Contest 121をPythonで解く

「AtCoder Beginner Contest 121」に出て、3完でした。

atcoder.jp

C問題まで順調に解けたのですが、D問題でTLEした後、O(1)の解法が分かりませんでした。

A - White Cells（100点）

• h個の行とw個の列をそれぞれ一番端まで動かしても答えは変わらない

H, W = list(map(int, input().split()))
h, w = list(map(int, input().split()))

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

B - Can you solve this?（200点）

• 要件通りに実装

N, M, C = list(map(int, input().split()))
B = list(map(int, input().split()))
A = []
for i in range(N):
    A.append(list(map(int, input().split())))

def main():
    cnt = 0
    for i in range(N):
        val = C
        for j in range(M):
            val += A[i][j] * B[j]
        if val > 0:
            cnt += 1
    return cnt

print(main())

C - Energy Drink Collector（300点）

• 安い店から買い尽くしていく
• 多重リストのソートで実装

from operator import itemgetter


N, M = list(map(int, input().split()))

a = []
for i in range(N):
    a.append(list(map(int, input().split())))

def main():
    b = sorted(a, key=itemgetter(0))
    # print(b)
    m = 0
    cost = 0
    for i in range(N):
        # print(b[i])
        if (m + b[i][1]) <= M:
            m += b[i][1]
            cost += (b[i][0] * b[i][1])
        else:
            cost += (b[i][0] * (M-m))
            return cost
    return cost

print(main())

D - XOR World（400点）

• 次の実装がTLEになって、思考停止

from functools import reduce
from operator import xor


A, B = list(map(int, input().split()))

def main():
    val = []
    for i in range(A, B+1):
        val.append(i)
    ans = reduce(xor, val)
    return ans

print(main())

復習

D問題

• 愚直に実験していけば、規則性が見いだせた
• きちんと手を動かして考える大切さを改めて実感した

A, B = list(map(int, input().split()))
 
def get(x):
    return [x, 1, x + 1, 0][x % 4]
 
def main():
    return get(B) ^ get(A - 1)
 
print(main())