ABC121 メモ

A - White Cells

答えは$(H-h)(W-w)$

121A.py

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

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

B - Can you solve this?

問題文通り愚直に判定を行う。

計算量は$O(NM)$より問題なし。

121B.py

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

ans = 0
for i in range(N):
    Alst = list(map(int, input().split()))
    tmp = C
    for j in range(M):
        tmp += Alst[j]*Blst[j]

    if tmp > 0:
        ans += 1

print(ans)

C - Energy Drink Collector

栄養ドリンクを買う順番によらず、安い店で買えるだけ買うのが最善。

実装上は、値段と本数を組にしたリストをソートし、安い方からM本超えるまで足し上げていく。

計算量は、ソート部が$O(N\log{N})$、足し上げ部が$O(N)$より、全体では$O(N\log{N})$。

121C.py

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

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

cnt = 0
ans = 0
lst.sort()

for i in range(N):
    A, B = lst[i]
    if cnt + B < M:
        cnt += B
        ans += A*B

    else:
        ans += A*(M-cnt)
        break

print(ans)

D - XOR World

今回の問題ではA, Bが十分大きいため、そのままAからBまでXORを計算しては間に合いません。

このような場合、XORをとる数字を二進数に変換した際に各位の1の個数の偶奇を計算することを考えた（偶数子ならその位は1、そうでなければ0）。

また、XORの性質として、A xor A = 0であるから、AからBまでのXORは、1からBまでのXORと、1からA-1までのXORでXORを計算することで、求まることが分かる。

よって、1からNまでのXORを計算する関数を作れば解けることが分かった。

ここで、二進数を列挙していくと、

十進数	二進数
0	0000
1	0001
2	0010
3	0011
4	0100
5	0101
6	0110
7	0111
8	1000
9	1001
10	1010
11	1011
12	1100
13	1101

のようになり、各位が周期的に変化していることが分かる。右からi番目の位は、$2^{i}$個で一周するので、これを利用して、Nの各位の周期の中で1が何個現れている部分かを判別して計算を行うことができた。

計算量については、$10^{12}<2^{40}$なので、高々40回程度の計算でいいことがわかる。よって$O(\log{max(A, B)})$である。

公式の解説の方がより単純で実装も楽だった。

121D.py

def xor_sigma(N):
    n = 0
    for i in range(40):
        if i == 0:
            if N%4 == 1 or N%4 == 2:
                m = 1
            else:
                m = 0

        else:
            d = N%(2**(i+1))
            if d%2 == 1 or d < 2**i:
                m = 0
            else:
                m = 1 << i

        n = n|m

    return n

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

ans = xor_sigma(A-1)^xor_sigma(B)
print(ans)