差分
このページの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 | ||
---|---|---|---|
行 5: | 行 5: | ||
* [[https:// | * [[https:// | ||
- | C問題までは考察より実装。B問題はPythonならNumPy使えと言われた気がした。 | + | |
+ | ===== 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 ===== | ||
行 54: | 行 111: | ||
それ以外の部分は $N$ が奇数の時0となり、偶数の時は $N$ のままとなる。 | それ以外の部分は $N$ が奇数の時0となり、偶数の時は $N$ のままとなる。 | ||
- | D問題にしては、わりと実験しやすく法則も気付けば単純なので、正解率は高かった模様。 | + | D問題にしては、わりと実験しやすく法則も気付けば単純なので、正解率は高かった模様。証明は解説pdfがエレガント。 |
<sxh python> | <sxh python> |