Lepton https://blog.hatena.ne.jp/Lepton/ Particle https://lepton.hatenablog.jp/ X = 0 であるときは、a/b が大きい方が前に来るようにすればよい。 前半・後半に分ける集合を固定したときも、それぞれの集合内では、a/b が大きい方が前に来るのが最適となっている。 あとは、前半・後半にどう分けるかが問題となるのだが、a/b でソートして、後半部分の b の合計を固定すると DP で計算することができる。 自分の実装では、a/b で降順にソートし、前半・後半部分の後ろから敷き詰めていくような DP で解いた。(4 次元の状態数を持つことになるので MLE に注意する) 計算量は、O(N^4*maxB^2)で、少しだけシビアなので、あまり定数倍が重くなりすぎないようにする。… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Flepton.hatenablog.jp%2Fentry%2F2018%2F02%2F16%2F224750" title="SRM 691 Div1 Medium Moneymanager - Particle" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2018-02-16 22:47:50 rich https://lepton.hatenablog.jp/entry/2018/02/16/224750 1.0 100%