脳log[20211027]

2021年10月27日 (水) [AtCoder] 精進。ABC169-F「Knapsack for All Subsets」(青 diff)。よくある DP をすると TLE が必至なので、A 数列の同じ値を和と場合の数にまとめてから頑張って掛け合わせた。提出 #26852407 (AC / 798 Byte / 841 ms)。そしたらね、Ruby で断トツ一番速い提出がこれ>#13965887 (195 ms)。numo/narray ですって。それ以外の提出は 600 ms 台に先頭集団がある他は１秒オーバーがほとんどなんだけど(「Ruby によるすべての提出」)、長さに関してはどの提出も自分の 798 Byte より短い。何か見落としがある！ これが短くて速い代表的な提出だけどほとんどワンライナー>#18041479。どういうことなの？ ×２するところを÷２にすることで要素の更新が省略できて速いらしいんだけど、そもそも持っているデータが違うから×２も÷２もないんだよね。■繰り返される配列の確保と初期化が重かったのでできるだけ短い配列で済ませるようにした>提出 #26862342 (AC / 717 Byte / 679 ms)。考察がへぼでも 600 ms 台に入った。添字 1 から A の値未満のところは初期値から更新されないので不要なのだけど、添字 0 のところに意味のある値が入っているのが邪魔。配列をローテーションしてから長さを切り詰めている。難解。へぼな考察を実装でごり押ししているのが悪い。