415.1

こんなのできるデータ構造ないですか？みたいなメールを書いている途中で、適切なデータ構造というか変形を思い付いたので、気合いで最適化していた。何やっているんだろうね...。

500

N個の商品から価値の合計がKになるように買うときにかかる最小の費用を答えよ、という問題。(再掲)

先頭と尻尾に分けて計算して、バイナリサーチで最小費用を見積もる、という方針のまま最適化。Nは高々16個なので、65536の配列が二つできます。先頭の方は価値の高い順に、尻尾の方は価値の低い順に並べます。

このままだと、65536*65536の計算をしないといけなくなってしまうので、尻尾のリストを改造します。先頭側でどれを採用するか決めると、尻尾側では、最低限必要な価値がどれくらいかわかります。なので、尻尾のリストを作り変えて、価値と値段ではなく、最低限この価値を実現するのに必要な値段、つまり自分よりも後ろにあるのが安ければ、そいつで値段を上書きするということをやります。

後は両方を見比べて行って、価値の合計が目的値を上回るようになったときに、予算内かどうかを判定するだけ。

最初はバイナリサーチ中で、使えるお金でフィルタしながら配列を再構成していたけれど、それが非常に重かった。実はデータ構造の変更はいらなかったのかも。