WEB系エンジニアの勉強日記

Baby steps to Giant strides!

Atcoder Beginner Contest 032

Tasks - AtCoder Beginner Contest 032 | AtCoder

A, Bは問題なく解けた。

C

愚直に解くと、すべての開始点から条件内に収まる限り部分文字列をインクリメントしていく方法([tex:N2])で解けそう。

開始点をインクリメントする際に、部分列の積をまた始めから計算しなおすのではなく、一つ前の値で割ることで、無駄な計算を省くことができる。(O(N))

D

ナップサック問題

蟻本でやったことがあったので簡単に解けるかなと思ったが、3つのパターンそれぞれ解法を考える必要があるということで、本の内容より複雑で苦戦した。

なので、DPを解く際に気をつけることを整理。

  1. 差分がどういった方式で求めることができるかを明確にする。(明確にできない場合はDPは差分方程式のDPは使わない)
  2. 上記で明確にした内容からDPの初期値を決める。

N が小さい場合の解法

Nが小さく、W, V が大きい場合に上記のDPは使えない。

N <= 30 なので、230 だと大きすぎるので、荷物を半分に分割し、前半後半部分の組み合わせを工夫することで、計算量を抑える。

まず前半部分荷物の全組み合わせを集計し、後半部分で、残りの重さでの二分探索ができるように整理する。

(重さでソートした後に、より低い重量で、高い価値があるような組み合わせは排除する。vectorの2分探索は lower_bound で求めることが可能)

後半部分の組み合わせ集計後に、残り重量でのベストな前半部分の価値を二分探索で求め、足し合わせたものの中から MAX を求める。