目次
AtCoder Beginner Contest 121 D問題メモ
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))
