1 of 5

F: Insane Crane Game

FA(全体): team05 (10:39)

FA(オンサイト): Maximum_Bandaisan (23:12)

AC/Tries: 24/42

​

原案: lmori

​

​

​

​

2 of 5

問題概要

  • N個の区間がある。次の行動を1回行う

​

数直線上の好きなL, Rを選び、[L, R] に完全に含まれる区間の数をスコアとして得る

​

  • K以上のスコアを得られる最小の[L, R]の区間幅を出力

​

この解説では、入力で与えられる区間[X_i - D_i, X_i + D_i] を [L_i, R_i ] と表記しています。

3 of 5

観察

  • Rを固定してLを探索する方針
  • 解の候補となるRは、いずれかの区間のR_iと一致する
    • そうでないと仮定したら、R_iに一致するまでRを縮めることができるので矛盾
  • Rに対して、K個以上の区間を含むまでLをギリギリまで伸ばしたい

4 of 5

解法

  • 与えられた区間を右端で昇順ソートする
  • データ構造に値を加算しながら、二分探索で[x, r_i] の区間和がK以上となる最大のxを求める
  • 各区間で求めた区間幅の中で、最小の値が答え

BIT / Segtree + 二分探索

5 of 5

時間計算量

与えられる区間の個数はN個あり、二分探索パートはBIT / SegTree を用いてO(logN) で可能。

よって、この問題をO(NlogN)で解くことができた。