AtCoder Regular Contest 101 参加記

1ヶ月ぶりくらいかつ8月最後のrated,久しぶりのコンテストでめちゃくちゃ緊張してた

C問題 Candles

問題

C - Candles

解法

sortedなので全部の[x,x+m)について距離を求めていけば良い.O(N)
デバッグ出力は消しましょう(何回目だおい

D問題 Median of Medians

解法

  • 素数Nの数列の中央値は,x以上の値がN/2個ある数のうち最小のもの

→二分探索で探せる形

  • 区間の中央値がx以上であるということは,その区間に存在するx以上の要素の個数がx未満の要素の個数より少なくないということ.

x以上のものを+1,x未満のものを-1として累積和を取ると(区間のx以上の要素数)-(区間のx未満の要素数)が求まる
ここまででオーダーをO(N^2log N)に落とすことができた.(まだTLE)

  • 区間(区間のx以上の要素数)-(区間のx未満の要素数)が非負であればよいので,各終端についてそれより前でそれ以下のものを探せば良い.これはBITで可能.

ここまでやるとオーダーがO(N log^2N)になって通る.

結果

f:id:SugarDragon5:20180825231520p:plain
青コーダーになりました.まじで時間かかった.嬉しい