一応解けた。問題としては制約無制限のナップザックを $ N \leq 48 $ で解こうというもの。
一応ACしたものの、最悪のケースについては遅くなってしまう。 そのケースが入ってたら、おそらくTLEかMLEしてたと思う。 ただ、ランダムケースならかなり速いコードを書けているのは、ACしたことで証明できているんじゃないかと思う。
まず全体の方針として半分全列挙が必要。ただ、半分全列挙をすると言っても、 愚直にやるのではなく、現在のデータと新たに作ったデータをマージするようなやり方で、 $ \mathrm{O}(N 2^{N/2}) $ を $ \mathrm{O}(2^{N/2}) $ にすることを実現している。 AtCoderのある問題の解説 などをみるとこれについては理解できると思う。
これで通るのかなと思っていたが、MLEを多発してしまった。 まず半分全列挙に必要な加算済みのデータは $ 2^{24} $ 個あり、これを long long の 配列で少なくとも 6 つは作らないといけなかった。 これはメモリ制限の 256MB に引っかかってしまう。
ここで、マージの最中に今まで出てきた価値の最大のもの以下の価値を持つものは省くという処理を思いつく。 マージする際に出てくるデータの順は重さが小さい順になっている。 この際、今まで出てきた価値よりも小さいものを入れても、それより軽い、価値がそれ以上のものがあるので、 それを使えばいいということがわかる。そのため、省いていい。
これを $N/2$ 回のマージの最中に何度も行えるので、ランダムケースならかなりデータが省けるのではないかと 期待した。実際に劇的に速くなった。
そして、最悪のケースの例だが、価値と重さが同じであり、全く総和がかぶらないようなものだ。 例えば、
48 1000000000000000 1 1 2 2 4 4 8 8 16 16 ... 2^47 2^47
みたいなケースだろう。
この場合、どのようにしても価値と重さがかぶらないので、半分全列挙の２つの配列は しっかり $ 2^{24} $ 個確保されてしまう。だけれどもこんなケースはほぼない上に、 例えば先に上げたケースだったらうまく例外処理すれば速く解けるのだと思う。 あーでも、重さと価値がちゃんと昇順になっているケースには弱いのかな。ちょっとわからない。
個人的にはナップザックに対して何をすればかなり速くなるのかがわかったのでちょっと満足している。 特有の性質だしね。 それに、前に解こうとして、ずっと解けてなくてもやもやしてたのが解消できたかな。
(2023/09/15 11:05)普通の全列挙でも通った。この手法はかなり速いみたいだ。多分平均計算量的なのが小さい。 問題のタグを見てみると「全列挙」と「ソート」しか書いてないから、ソートの工夫をすれば 普通の全列挙で通るという示唆なのかもなんて考え過ぎか。
(2023/09/15 18:08)重みが同じものがあるときに価値が最大のものだけ入れればいいということもわかるので それも実装した。こうすると重みの総和としてあり得る値の数あるいは価値の総和としてあり得る値の数 よりも小さいものしか配列に入らなくなるので、DPで解くような $N$ の大きい ナップザック問題も解けるようになる。
制限なしでもそれなりに速いということもあるので結構汎用的なものができた。 そのためライブラリにしてみた。
ソースコードはこのような感じになった。だいたいなんでも使えるのは強いと思う。
このAtCoderの問題 を解こうと思って、 重みもかぶらないようにすることを思いついた。ここまで汎用的なものになるなんて思わなかった。 また思いついたらなにか書こうと思う。
(2023/09/15 21:56)