差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2019:0309_abc121 [2019/03/09] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2019:0309_abc121 [2019/03/09] (現在) – ikatakos | ||
|---|---|---|---|
| 行 3: | 行 3: | ||
| [[https:// | [[https:// | ||
| + | * [[https:// | ||
| + | |||
| + | |||
| + | ===== B - Can you solve this? ===== | ||
| + | |||
| + | [[https:// | ||
| + | |||
| + | ==== 解法 ==== | ||
| + | |||
| + | そのまま実装すれば良い。 | ||
| + | |||
| + | <sxh python> | ||
| + | import numpy as np | ||
| + | |||
| + | n, m, c = map(int, input().split()) | ||
| + | bbb = np.fromiter(map(int, | ||
| + | ans = 0 | ||
| + | for _ in range(n): | ||
| + | aaa = np.fromiter(map(int, | ||
| + | if sum(aaa * bbb) + c > 0: | ||
| + | ans += 1 | ||
| + | print(ans) | ||
| + | </ | ||
| + | |||
| + | |||
| + | ===== C - Energy Drink Collector ===== | ||
| + | |||
| + | [[https:// | ||
| + | |||
| + | ==== 問題 ==== | ||
| + | |||
| + | * エナジードリンクを売る店が $N$ 軒ある | ||
| + | * $i$ 番目の店はエナジードリンクを $A_i$ 円で $B_i$ 個売っている | ||
| + | * $M$ 個のエナジードリンクを集めたい時、かかる最小費用を求めよ | ||
| + | |||
| + | ==== 解法 ==== | ||
| + | |||
| + | 安い店から買えるだけ買う、という方針を素直に実装する。 | ||
| + | |||
| + | 安い店順に並べるには入力をリストや辞書に溜めて、ソートする。Pythonの場合はcollections.defaultdictを使うと、同じ金額の店をまとめる記述が書きやすくなる。 | ||
| + | |||
| + | <sxh python> | ||
| + | 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 ===== | ===== D - XOR World ===== | ||
| 行 13: | 行 73: | ||
| * $\oplus$ を、排他的論理和の演算子とする | * $\oplus$ を、排他的論理和の演算子とする | ||
| * $f(A,B)=A \oplus (A+1) \oplus ... \oplus B$ を求めよ | * $f(A,B)=A \oplus (A+1) \oplus ... \oplus B$ を求めよ | ||
| - | * $0 \le A \lt B \le 10^{12}$ | + | * $0 \le A \le B \le 10^{12}$ |
| ==== 解法 ==== | ==== 解法 ==== | ||
| まず排他的論理和の性質から、$f(A, | まず排他的論理和の性質から、$f(A, | ||
| + | |||
| + | f(1, | ||
| + | XOR f(1, B): 1 | ||
| + | ---------------------------------------------------- | ||
| + | `-- 打ち消し合う --' | ||
| なので、1から$N$ までの累積排他的論理和が求められればよい。 | なので、1から$N$ までの累積排他的論理和が求められればよい。 | ||
| 行 46: | 行 111: | ||
| それ以外の部分は $N$ が奇数の時0となり、偶数の時は $N$ のままとなる。 | それ以外の部分は $N$ が奇数の時0となり、偶数の時は $N$ のままとなる。 | ||
| - | D問題にしては、わりと実験しやすくすぐに法則が見えるので、正解率は高かった模様。 | + | D問題にしては、わりと実験しやすく法則も気付けば単純なので、正解率は高かった模様。証明は解説pdfがエレガント。 |
| <sxh python> | <sxh python> | ||
