0x19f (Shinya Kato) の日報

主にプログラミング関連の話をします

7/24 AGC018とか

AtCoder Grand Contest 018

安定の1完(). A問題が難しくて普通にお葬式になるところだった. Bは言われれば貪欲だなぁ〜って感じ.

 

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)になる.