脳log[20241010]

2024年10月10日 (木) [AtCoder] 精進。先週末あった ABC374-E Sensor Optimization Dilemma 2。「解けるんだからネタバレは嫌だ」とは書いたものの手詰まりだったので、Ruby の AC スクリプトをダウンロードしてきて見つけたダメケースを参考にデバッグをした。■TLE×4、TLE×1 のち AC (334 Byte / 1285 ms)。A*B ないし LCM(A,B) の単位では最適な比率が確定するだろうというのが自分の解法の根幹にあったのだけど、そうではなかった。解が W だとして W の周辺 A*B ないし LCM(A,B) の範囲に最適な比率があるというのが正解だった。たぶんね(←それだからお前は……)。TLE×4 の原因は LCM(A,B) ではなくより大きな A*B を使っていたこと。TLE×1 の原因は心当たりが２つあって、１つは二分探索の上限が X によらず一定だったこと。X に依存するようにして最大の場合でも 10 進１桁だけ上限が小さくなるようにした(けど二分探索の回数が３回減るくらいしか期待できなくない？)。２つ目が二分探索の判定を早期に打ち切るようにしたこと。全部を足してから判定するのではなく、累積値がボーダーを超えたらすぐにリターンする。こんなしょうもない定数倍の改善が AC するために求められるのはつらいなあと思ったら、Ruby で提出している他の皆さんは 79 から 931 ms の範囲で AC を出していて、中央値も平均も 120 から 130 ms のあたりにあるみたいだった。自分が桁違いに遅いだけだった。