脳log[20230106]

2023年01月06日 (金) [AtCoder] 精進。以前埋めきれなかった古い ABC から。ABC054-D「Mixing Experiment」(ぎりぎり青 diff)。以前書いた。「半分全列挙の問題が半分全列挙だと教えられる前に解けたためしがない」。それも今日で終わり。提出 #37756034 (AC / 562 Byte / 62 ms)。■Ruby によるすべての提出を見てるんだけど、別に半分にする必要はないっぽい？ 無駄半分無意味全列挙？ 速い提出を見ると A 過剰と B 過剰に分類してからそれぞれで組み合わせている。アイディアは近い、でもそっちの方がかしこーい、と思ったんだけど、全部が一方に偏っているときに組み合わせがやばそうなので機械的に半分にする方がいいかな。もっとも、N<=40 なので N^3 でもやばくはないし、なんならすべての和が分布する 400×400 の平面上の格子点をしらみつぶしに調べても良かったらしいけど。他には a*Mb-b*Ma という式を複数の速い提出で見かけた。比例式のような外積のような？ 実行前のオーバーヘッドが Ruby 2.7 より小さい Ruby 2.3 であることを差し引いても 12 ms や 27 ms は速いのでは。■提出 #37756578 (AC / 416 Byte / 60 ms)。テキトーにさっきの式をパクってみたらそれでも AC になった。式の意味がわからない。じゃあ最初の提出では何をやっていたかというと、a と b のペアから MA 対 MB の比率ですでに完成した物質 C を取り除いたときに a と b がそれぞれどれだけ過剰かを１つの値にエンコードして DP のキーにしていた。そのキーを例の謎の式にすると a と b の値をデコードする必要がなくなってエンコードした値そのもので演算ができるらしい。謎。