脳log[20210915]

2021年09月15日 (水) [AtCoder] 精進。ARC073-D「Simple Knapsack」(水 diff)。タイトルに騙されて制約も見ずに DP 用の配列を大きさ W で確保しようとしたら、サイズ１ギガの配列は大きすぎると Ruby に怒られた。Simple とは……。難しく考えて再帰関数で 64 ms の提出(#25855795)を作ったのだけど、これって DP からの退行では？ Ruby のバージョン違いによるオーバーヘッドの差があるからそのままの数字を比較できないけど、連想配列で普通に DP をしても 30 ms で済んでいる>#11970957。そしてこちらのこの方は自分と同じく DFS を採用してらっしゃる>#25853638 (今日の提出)。AtCoder Problems で Ruby による最近の提出一覧を見て今日の一問を選んだのです。中身までは見てなかったので似てるのは問題から導かれる必然であり偶然の結果です。違うところは、ある重さのアイテムの採用数を一定レベルより下げても、他の重さのアイテムの採用数が上限に達して増やせなくなるポイントがあるので、その均衡点を見極めてループを打ち切っているところ。それが難しく考え過ぎだっていうんだけど、想定解が 400^3 のループで Ruby 勢を虐殺した ABC-D の恨みが記憶に新しいせいなんだよなあ。