コンテスト後のツイート
E どのindexでレベルアップするかをkごとに記録。SortedSetを使ったらTLEしてしまったけれど、SortedSetを使ってACしている人もいるようなので、実装が下手。まあ、調和級数のlogとSortedSetのルートがつくので計算量的にも結構厳しそうではあるんだよね。
— titia (@titia_til) July 30, 2024
E. Level Up
SortedSetをセグ木上の二分探索に直してAC。
自分のセグ木二分探索のライブラリの書き方が変だったので、修正に時間を要したけど、どう書くのが良いのだろう？
とりあえず、セグ木の演算が足し算で、
・sum(0, index)がある値以上になる最初のindexを返す
というセグ木二分探索は実装した。
一般的には何を二分探索で求めるようにすれば良いんだろう？
0 件のコメント:
コメントを投稿