中央値
BIT木。初見で解いているときは BIT木を知らなくて TLE を出し続け、諦めて解説読んでナニコレとなった。 BIT木の使いどころは、BIT木を2本持つことで、小さい方から i 番目の値の探索を log(N) を行える点である。値の追加、探索、削除を log(N) でできるの…
Eまで5完。Fが形式的冪級数だと気づきさえすれば6完できたのに。 Bは0が後ろにあるケースがサンプルにあったからすぐ修正できた。sort したら前から10**18 を超えたら -1 を出力するようにプログラミングしてよい。python は10**18の計算をしてもエラー吐…
atcoder.jp要約すると Σ|Ai-b| (0≤i≤n) を最小にするbがわかるかどうかという問題。 ネタバレすると Ai (0≤i≤n) の中央値が答えとなる。知らなかった。 例題の出力をみて、入力と同じものになっていることに気づくべきだった。 分かりやすい図説があったので…