naoya_t@hatenablog

いわゆるチラシノウラであります

AtCoder Regular Contest 101

8/25 21:00〜22:40
久々のratedなコンテスト。
1完...
レートは微増(1759→1776)

C - Candles (300)

  • (右からか左からかは別として)連続で点火するしかない
  • 長さKの区間を全部試す
  • 右からか左からの早い方

→AC 6'06''
https://beta.atcoder.jp/contests/arc101/submissions/3073038
割とすんなり通せた

D - Median of Medians (700)

  • 最初問題を誤読していた(aをソートしてた)
  • aそのままで、計算量減らすにはどうしたらいいか
  • 1時間半悩んだ
  • 終了

追記】解説読んだ

  • 答えのxを二分探索
  • xがあるとするとこういう性質、というのは分かっていて
    • M={}_{N+1}C_2 で ceil(M/2) 個以上、x以上の数がある
    • x決め打ちにすれば、x未満を-1、x以上を+1とすることで累積和をとって転倒数のカウントを利用して求められる

→TLE
https://beta.atcoder.jp/contests/arc101/submissions/3081089
あー自作転倒数ライブラリが遅すぎる(N=1e5でローカルで10秒弱かかる…)

Fenwick Tree (BIT) を使って転倒数カウント部分を書き直して
// (座圧したものを)右から走査して、今の数未満の数がいくつ右側で既出かのカウントをFTで求めて答えに足し、FTに今の数を+1追加するやつ
→AC
https://beta.atcoder.jp/contests/arc101/submissions/3081487

E - Ribbons on Tree (900)

問題は読んだ

F - Robots and Exits (900)

開いてない