脳log[20220718]

2022年07月18日 (月) [AtCoder] 精進。ARC144-B「Gift Tax」(緑 diff)。AtCoder Problems に Easy 問題を推薦してもらったら出てきたんです。まだ解いていない緑 diff はどれも解こうとしたけど解けなかった問題として名前を覚えてるんだけど、これは見覚えがなかった。■提出 #33348708 (AC / 177 Byte / 1181 ms)。おとつい１時間溶かして解けなかった問題じゃん。そのときも二分探索は書いていたし、A と B で割る二種類の割り算も書いていた。でもサンプルの４が合わせられなかった。なんで今日は AC なんだろうね、不思議だね。■まじめに書くと、おとついと今日では二分探索で探ろうとしていたボーダーの意味が違う。おとついはいったん増減の幅が a,b に固定されていることを忘れて、a 対 b の比率を保ったまま定まる平均値を求めようとしていた。でもそこから答えに近づけなかった。今日はまず、答えとなる最小値を二分探索で決め打ってから、必要となる数列を増加させる回数を求め、同じ回数を減少させるときに数列が維持できる水準(どの値より上を切り捨てるか)を二分探索した。２つの二分探索による２つの水準が逆転するならそれは矛盾であり答えとして成立しない。この考え(ARC144_b_TLE.rb27)は間違いではなかったけど、二重の二分探索に線形時間のスキャンが重なるので数十秒の時間がかかって TLE が必至。AC 提出は log を１つ外そうと最適化した結果であり、最初からあの形が頭の中にあったわけではなかった。直接最適な答えが導き出せないあたり、力が及んでおらず本番で解けないのも仕方のないことかもね。