AtCoder ABC121 参戦記

今回はちゃんと全完できました。最近3000人以上参加しててびっくりです。以下提出コードと軽い解説。

A問題 (White Cells)

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

数学(算数?)の問題です。

B問題 (Can you solve this?)

N, M, C = map(int, input().split())
B = [int(b) for b in input().split()]
Count = 0
for _ in range(N):
    A = [int(a) for a in input().split()]
    Total = C
    for i in range(M):
        Total += A[i] * B[i]
    if Total > 0: Count += 1
print(Count)

M個のクエリに対して実際に判別式を解いてやります。

今回の制約はN, M共に20以下なのでO(NM)でも十分に高速に解けます。

C問題 (Energy drink collecctor)

N, M = map(int, input().split())
Drink = [[int(i) for i in input().split()] for _ in range(N)]
Drink.sort()
 
Need = M
Payment = 0
for i in range(N):
    if Need > Drink[i][1]:
        Payment += Drink[i][0] * Drink[i][1]
        Need -= Drink[i][1]
    else:
        Payment += Drink[i][0] * Need
        break
print(Payment)

このエナジードリンク欲しいですよね。

安い順に買っていくのが最適であることはすぐにわかると思います。

リストに[値段、個数]を格納し、ソートすることで安い順に並び替えることができます。

あとはM個買えるまで安い方から買っていきます。

D問題 (XOR world)

A, B = map(int, input().split())
 
Bit = [0] * 40
ai, aj, bi, bj = A//2, A%2, B//2, B%2
one = (bi - ai) + bj
Bit[0] = one % 2
 
for i in range(1, 40):
    two = 2 ** i
    ai, aj = A // two, A % two
    bi, bj = B // two, B % two
    if ai == bi and ai % 2 == 1: Total = bj - aj + 1
    else:
        Total = 0
        if ai % 2 == 1:
            Total +=  two - aj
        if bi % 2 == 1:
            Total +=  bj + 1
    if Total % 2 == 1: Bit[i] = 1
Ans = 0
for i in range(40):
    if Bit[i] == 1: Ans += 2 ** i
print(Ans)

解説みたいなスマートな解き方はしてません。

各Bit毎に１の個数の偶奇を判別し、奇数なら2ⁱを答えに足すというやり方をしています。

ではどう判断するか?

例えばA = 9, B = 42として2³(=8)の桁を見ることを考えます。

数字をn * 8 + mと現したときにnが同じものを一つのグループとして考えると、この場合は[1*8+1,1*8+7]、[2*8, 2*8+7]…[4*8,4*8+7],[5*8, 5*8+2]と分けることができます。

このうちnが偶数のグループは2³のbitが０であるため無視できます。

nが奇数でもn_A (= 1) < n < n_B (= 5)であるようなグループ([3*8, 3*8+7])は2³のbitが１ですが、要素も2³個あり、この要素内でXORをとると0になるので無視できます。

すると考えるべきグループは2³個揃わない可能性のある、AとBを含むグループのみであることがわかります。

これもn_A、n_Bが奇数の時のみ考えればよくて、この時それぞれ2³ - m_A、m_B＋１個2³のbitが1になります。

2^0の時だけ数え方が違うということと、n_A = n_Bかつn_Aが奇数の時は個数がm_B-m_A+1になることに注意して各桁同じように解いていきます。