7/24 AGC018とか
AtCoder Grand Contest 018
安定の1完(). A問題が難しくて普通にお葬式になるところだった. Bは言われれば貪欲だなぁ〜って感じ.
-
A: Getting Difference - AtCoder Grand Contest 018 | AtCoder [解答]
A問題なのに難しい. A[i]が{ dm | m = 1, 2, 3, ... }の部分列となるような最小のdを求めると, max(A[i])以下のdmで表される数は全て表現することができる. このようなdはd = gcd(A[0], A[1], ..., A[N - 1])で計算できる. ちゃんとした証明はしてないです. -
B: Sports Festival - AtCoder Grand Contest 018 | AtCoder [解答]
全部のスポーツを開催した状態から一番参加者が多いスポーツを減らしていくgreedy. 1個ずつ減らしながら最大の最小をとる.
ABC/ARC D問題埋め
- D: No Need - AtCoder Regular Contest 070 | AtCoder [解答]
部分点解法は, ある1枚のカードを抜いて部分和を列挙する. 和がK未満の部分集合に抜いたカードを入れて和がK以上になれば, そのカードは不要ではない. 抜くカードの選び方がN, 部分和の列挙がO(NK)なので, 全体で計算量はO(N^2 * K).
満点解法は, しばらく考えたのだけれどわからなくて解説を見てしまった. 実はカードを書かれている数字の昇順でソートすると, カードiが不要ならカード(i - 1)も不要となる. なので, 必要なカードと不要なカードの境界を二分探索する. もちろん, 二分探索の判定部分では部分和のDPをする. 全体としての計算量はO(logN * NK)になる.