脳log[20220126]

2022年01月26日 (水) [AtCoder] 精進。第八回 アルゴリズム実技検定-L「K番目の絶対値」 どうしても Nlog^2 の方法しか思いつかなくて TLE が避けられなかった。気がついてみれば単に累積和と二分探索を使うだけの典型も典型だった。自分がこれまで見て来なかったのは、累積和を使って定数時間で数列のある範囲の和を求めるというときに、添字の大小関係は絶対ではないということ。S[j]-S[i] で和を求めるときに、i<j でも j<i でも構わないということ。符号を入れ替えればいいだけ。そしてこの問題に関して言えば、問われているのが絶対値であることで符号の入れ替えさえ不要だった。絶対値が問題を面倒にしているとばかり思っていたぜ。■提出 #28807480 (AC / 232 Byte / 1853 ms)。累積和をソートすることも解を二分探索することも早くからわかっていた。二分探索の中で数列をスキャンする中で j<i となるケースを除外するために BIT なりで対数時間の処理を加えてしまうと Nlog^2 になって困ったなーと考えていた。事前にじっくり準備して BIT に頼らないデータ、それも N×N よりコンパクトなデータが作れないかなーと考えていた。実は j<i となるケースを除外する必要などなかった。累積和の使い方がわかっていない！ 精進の道とは自分のアホさを確認する道なのか。