差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン
前のリビジョン
programming_algorithm:contest_history:atcoder:2019:0309_abc121 [2019/03/09] – [解法] ikatakosprogramming_algorithm:contest_history:atcoder:2019:0309_abc121 [2019/03/09] (現在) ikatakos
行 5: 行 5:
   * [[https://www.youtube.com/watch?v=igfVeTsGeYw|AtCoder Beginner Contest 121 解説放送 - YouTube]]   * [[https://www.youtube.com/watch?v=igfVeTsGeYw|AtCoder Beginner Contest 121 解説放送 - YouTube]]
  
-C問題まで考察実装。B問題はPythonならNumPy使言われた気した+ 
 +===== B - Can you solve this? ===== 
 + 
 +[[https://beta.atcoder.jp/contests/abc121/tasks/abc121_b|B - Can you solve this?]] 
 + 
 +==== 解法 ==== 
 + 
 +そのまま実装すれば良い。 
 + 
 +<sxh python> 
 +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) 
 +</sxh> 
 + 
 + 
 +===== C - Energy Drink Collector ===== 
 + 
 +[[https://beta.atcoder.jp/contests/abc121/tasks/abc121_c|- Energy Drink Collector]] 
 + 
 +==== 問題 ==== 
 + 
 +  * エナジードリンクを売る店が $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) 
 +</sxh>
  
 ===== D - XOR World ===== ===== D - XOR World =====
行 54: 行 111:
 それ以外の部分は $N$ が奇数の時0となり、偶数の時は $N$ のままとなる。 それ以外の部分は $N$ が奇数の時0となり、偶数の時は $N$ のままとなる。
  
-D問題にしては、わりと実験しやすく法則も気付けば単純なので、正解率は高かった模様。+D問題にしては、わりと実験しやすく法則も気付けば単純なので、正解率は高かった模様。証明は解説pdfがエレガント
  
 <sxh python> <sxh python>
programming_algorithm/contest_history/atcoder/2019/0309_abc121.txt · 最終更新: 2019/03/09 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0