AtCoder Beginner Contest 121 D問題メモ

AtCoder Beginner Contest 121 解説放送 - YouTube

B - Can you solve this?

解法

そのまま実装すれば良い。

        
              import numpy as np
 
n, m, c = map(int, input().split())
bbb = np.fromiter(map(int, input().split()), dtype=np.int64)
ans = 0
for _ in range(n):
    aaa = np.fromiter(map(int, input().split()), dtype=np.int64)
    if sum(aaa * bbb) + c > 0:
        ans += 1
print(ans)

C - Energy Drink Collector

問題

エナジードリンクを売る店が $N$ 軒ある
$i$ 番目の店はエナジードリンクを $A_i$ 円で $B_i$ 個売っている
$M$ 個のエナジードリンクを集めたい時、かかる最小費用を求めよ

解法

安い店から買えるだけ買う、という方針を素直に実装する。

安い店順に並べるには入力をリストや辞書に溜めて、ソートする。Pythonの場合はcollections.defaultdictを使うと、同じ金額の店をまとめる記述が書きやすくなる。

        
              from collections import defaultdict
 
n, m = map(int, input().split())
ab = defaultdict(int)
for _ in range(n):
    a, b = map(int, input().split())
    ab[a] += b
 
ans = 0
remain = m
for k in sorted(ab.keys()):
    if remain <= ab[k]:
        ans += k * remain
        break
    ans += k * ab[k]
    remain -= ab[k]
print(ans)

D - XOR World

問題

2つの正整数 $A,B$ が与えられる
$\oplus$ を、排他的論理和の演算子とする
$f(A,B)=A \oplus (A+1) \oplus ... \oplus B$ を求めよ
$0 \le A \le B \le 10^{12}$

解法

まず排他的論理和の性質から、 $f(A,B) = f(1,B) \oplus f(1,A-1)$ である。

    f(1,A-1):  1   2   3 .. A-2 A-1
XOR f(1,  B):  1   2   3 .. A-2 A-1  A  A+1 ... B-1  B
----------------------------------------------------
               `-- 打ち消し合う --'  A  A+1 ... B-1  B

なので、1から $N$ までの累積排他的論理和が求められればよい。

実験してみる。すると、1桁目とそれ以外を分離すると、特徴が見えてくる。

 N     bit  f(1,N)
 0    0000    0000
 1    0001    0001
 2    0010    0011
 3    0011    0000
 4    0100    0100
 5    0101    0001
 6    0110    0111
 7    0111    0000
 8    1000    1000
 9    1001    0001
10    1010    1011
11    1011    0000
12    1100    1100
13    1101    0001
14    1110    1111
15    1111    0000
...

1桁目の部分は、2進数が0,1,0,1,…となるので、累積XORは0,1,1,0,…となる。

それ以外の部分は $N$ が奇数の時0となり、偶数の時は $N$ のままとなる。

D問題にしては、わりと実験しやすく法則も気付けば単純なので、正解率は高かった模様。証明は解説pdfがエレガント。

        
              a, b = map(int, input().split())
x = lambda n: (n % 4 in (1, 2)) + (0 if n % 2 else n // 2 * 2)
print(x(max(0, a - 1)) ^ x(b))