脳log[20240930]

2024年09月30日 (月) [AtCoder] 精進。おとといあった ABC373-F Knapsack with Diminishing Values。X で調和級数とのキーワードを見かけていた。ならば恐れずにやるだけかと思って愚直気味に書いたものは、N のループの中で W のループの中で飛び飛びに W をループするものであって、最大ケース (N=3000、W=3000、wi=1 (i=1..N)) がコードテストで 10 秒以上かかるものだった。飛び飛びに W をループするって書いたけど、重さが１のとき実は飛んでいなかった。調和級数と聞いて勝手に飛んでいる気になっていた。調和級数ってどういう式だっけ？ ループひとつの上限？ 二重ループの上限？■提出 #58293215 (AC / 510 Byte / 2001 ms)。重さの種類数と品物数が同数ということで、重さにはかなりの程度重複があると想定できる。重複なしにしようとすると重さは１から W の範囲に散らばることになって、重さが W に近づくほど同じ品物を１個までしか選べなくなるという点で好都合になる。だから重複はかなりの程度あると想定する。同じ重さの品物をまとめて扱いましょう。１個選ぶときの最大価値、２個選ぶとき(同じ商品を２個でも別の商品を１個ずつでも)の最大価値……を予め求めておく(６行目から 18 行目)。そうするとループの構造は変わらないけど、最外ループの回数が N から w の種類数に減って AC だった。想定解法かどうかはわからぬ。■Ruby ですでにある AC は l0rzl さんの提出 #58243889 (AC / 1429 ms) のみ。短いし 25 % 速いし、Rational を使ってソートしてるし、これはなんなんだろう。定数倍のハンデがあるにもかかわらず Array でなく Hash を使っていて速いというのは、重さの重複によってキーが限定される効果が大きいんだろうか(だけど w=1 を処理した時点で 0 から W まで全部埋まるよなあ)。優先順位を付けるのは、価値の低い品物が価値の高い品物が一度通った道を再度通らないように、とか？ ３重ループの構造は同じ。だけどそれぞれにループの回数を減らす工夫があって違う。■自分のは、どうせ 900 万だからと前処理を愚直にやっているので、そこをサボらずにやる手はある。だけどそうすると元から比較して長かったのがさらに長大化するのが必至。うまくないなあ。しかもプライオリティキューを使っても変わらんかった>提出 #58342271 (AC / 2012 ms)。たしかにメインループの外だから影響は小さいだろうけど、ゼロだとは思わなかった。