D - 街灯の暗い区間 / Dark Intervals of Street Lights 解説 by admin
gpt-5.5-high概要
各街灯が「暗い街灯」になる日を事前に求め、問い合わせの日数が小さい順に処理します。
暗い街灯が増えていく過程を管理しながら、暗い部分区間の個数を効率よく更新します。
考察
\(t\) 日後の \(i\) 番目の街灯の明るさは
\(C_i(t) = \max(0,\ A_i - D_i \times t)\)
です。
街灯の明るさは時間が進むほど下がるだけなので、一度「暗い街灯」になった街灯は、その後ずっと暗いままです。
つまり、各街灯について「初めて暗くなる日」を求めておけば、問い合わせを日数の昇順に処理することで、暗い街灯を順に追加していけばよいです。
街灯 \(i\) が暗くなる条件は
\(C_i(t) \leq K\)
です。
\(K \geq 0\) なので、\(A_i > K\) かつ \(D_i > 0\) の場合は、
\(A_i - D_i \times t \leq K\)
となる最小の \(t\) を求めればよく、
\(t = \left\lceil \frac{A_i - K}{D_i} \right\rceil\)
です。
一方で、
- \(A_i \leq K\) なら、最初から暗いので \(t = 0\)
- \(A_i > K\) かつ \(D_i = 0\) なら、永遠に暗くならない
です。
素朴に各問い合わせごとに全ての街灯を調べると、\(O(NQ)\) かかります。
\(N + Q \leq 2 \times 10^5\) なので、これは間に合いません。
そこで、街灯が暗くなる日をイベントとして管理し、問い合わせも日数順に並べます。
そして、まだ処理していないイベントのうち、問い合わせ日数以下のものを順に追加していきます。
次に、暗い部分区間の個数をどう更新するかを考えます。
連続する暗い街灯が \(m\) 本あるとき、その中から選べる部分区間は
\(\frac{m(m+1)}{2}\)
個です。
例えば、長さ \(3\) の暗い連続区間なら、
- 長さ \(1\) の区間が \(3\) 個
- 長さ \(2\) の区間が \(2\) 個
- 長さ \(3\) の区間が \(1\) 個
なので、合計 \(6 = \frac{3 \times 4}{2}\) 個です。
新しく位置 \(x\) の街灯が暗くなったとします。
その左側に長さ \(L\) の暗い連続区間があり、右側に長さ \(R\) の暗い連続区間がある場合を考えます。
追加前は、左と右は別々の区間です。
[暗い区間 長さ L] x [暗い区間 長さ R]
位置 \(x\) が暗くなると、これらが結合して長さ \(L + 1 + R\) の暗い区間になります。
このとき、新しく増える暗い部分区間の個数は
\((L+1)(R+1)\)
です。
理由は、新しく増える区間は必ず位置 \(x\) を含みます。
その左端は、左側の \(L\) 個の街灯または \(x\) 自身から選べるので \(L+1\) 通り、
右端は、右側の \(R\) 個の街灯または \(x\) 自身から選べるので \(R+1\) 通りです。
したがって、街灯を1本追加するたびに答えを
\((L+1)(R+1)\)
だけ増やせばよいです。
アルゴリズム
各街灯について、暗くなる日を求める
- \(A_i \leq K\) なら \(0\) 日目
- \(A_i > K\) かつ \(D_i > 0\) なら \(\left\lceil \frac{A_i - K}{D_i} \right\rceil\)
- \(A_i > K\) かつ \(D_i = 0\) なら暗くならないので無視
「暗くなる日」と「街灯の位置」をイベントとして配列に入れる
イベントを日数の昇順にソートする
問い合わせも \((T_j, j)\) の形で、日数の昇順にソートする
- \(j\) は元の問い合わせ番号
- 最後に元の順番で答えるために必要
現在の暗い部分区間の個数を
totalとして持つ各問い合わせ \(T\) について、
- 暗くなる日が \(T\) 以下のイベントをすべて処理する
- 街灯 \(x\) を暗い状態に追加する
- 左右に隣接する暗い連続区間の長さを調べる
total += (left_len + 1) * (right_len + 1)で更新する- 結合後の区間の長さを記録する
その時点の
totalが、問い合わせ \(T\) に対する答え
コードでは、暗い街灯かどうかを active で管理しています。
また、連続区間の長さは seg_len に保存しています。
ただし、すべての場所に長さを入れる必要はなく、区間の両端だけに長さを持たせています。
例えば、長さ \(4\) の暗い区間が位置 \(2\) から \(5\) にある場合、
位置: 0 1 2 3 4 5 6
active: 0 0 1 1 1 1 0
seg_len: 0 0 4 0 0 4 0
のように、左端と右端だけに長さ \(4\) を保存します。
新しく位置 \(x\) を追加するとき、
- 左隣 \(x-1\) が暗いなら、そこは左側区間の右端なので
seg_len[x-1]から長さが分かる - 右隣 \(x+1\) が暗いなら、そこは右側区間の左端なので
seg_len[x+1]から長さが分かる
という仕組みです。
計算量
- 時間計算量: \(O((N+Q)\log(N+Q))\)
- 空間計算量: \(O(N+Q)\)
イベントのソートと問い合わせのソートに \(O((N+Q)\log(N+Q))\) かかります。
各街灯の追加処理は高々1回なので、更新部分全体は \(O(N)\) です。
実装のポイント
暗くなる日の計算では、切り上げ除算を使います。
\(\left\lceil \frac{A_i - K}{D_i} \right\rceil\)
は整数演算で
(A - K + D - 1) // D
と書けます。
また、答えは最大でかなり大きくなるため、64ビット整数が必要です。
Python では整数が任意精度なので特に気にする必要はありません。
ソースコード
import sys
def main():
data = list(map(int, sys.stdin.buffer.read().split()))
idx = 0
N = data[idx]
Q = data[idx + 1]
K = data[idx + 2]
idx += 3
events = []
for i in range(N):
A = data[idx]
D = data[idx + 1]
idx += 2
if A <= K:
events.append((0, i))
elif D > 0:
t = (A - K + D - 1) // D
events.append((t, i))
queries = []
for j in range(Q):
T = data[idx]
idx += 1
queries.append((T, j))
events.sort()
queries.sort()
active = bytearray(N)
seg_len = [0] * N
ans = [0] * Q
total = 0
e = 0
m = len(events)
for T, qi in queries:
while e < m and events[e][0] <= T:
x = events[e][1]
e += 1
left_len = 0
right_len = 0
if x > 0 and active[x - 1]:
left_len = seg_len[x - 1]
if x + 1 < N and active[x + 1]:
right_len = seg_len[x + 1]
total += (left_len + 1) * (right_len + 1)
new_len = left_len + right_len + 1
seg_len[x - left_len] = new_len
seg_len[x + right_len] = new_len
active[x] = 1
ans[qi] = total
sys.stdout.write("\n".join(map(str, ans)))
if __name__ == "__main__":
main()
この解説は gpt-5.5-high によって生成されました。