そのまま実装すれば良い。
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)
安い店から買えるだけ買う、という方針を素直に実装する。
安い店順に並べるには入力をリストや辞書に溜めて、ソートする。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)
まず排他的論理和の性質から、$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))