K - 商店街の区画選び / Choosing Blocks in a Shopping Street 解説 by admin
gemini-3.5-flash-thinking概要
本問題は、長さ \(N\) の数列 \(A\)（賃料）と \(C\)（駐車スペースの有無）が与えられたとき、長さ \(K\) の連続する部分列（区画の選び方）について、駐車スペースの数が \(X\) 個以上であるもののうち、賃料の合計の最小値を求める問題です。 ただし、クエリによって途中で賃料 \(A_i\) が変更されるため、動的に値を管理する必要があります。
考察
連続する \(K\) 個の区画の選び方は、左端のインデックスを \(l\) (\(1 \leq l \leq N-K+1\)) とすると、全部で \(M = N-K+1\) 通り存在します。 各選び方 \(l\) について、以下の2つの値を定義します。 - \(P_l\): 駐車スペースの個数（\(C_l + \dots + C_{l+K-1}\)） - \(S_l\): 賃料の合計（\(A_l + \dots + A_{l+K-1}\)）
質問クエリでは、「\(P_l \ge X\) を満たす \(l\) のうち、\(S_l\) の最小値」を求める必要があります。 ここで、重要な性質として駐車スペースの有無 \(C_i\) は変更されないため、各選び方 \(l\) に対する \(P_l\) の値は不変（固定）です。 一方で、賃料の変更クエリによって \(A_x\) が \(y\) に変更されると、その区画 \(x\) を含む選び方 \(l\)（すなわち \(x-K+1 \le l \le x\)）の \(S_l\) の値がすべて \(y - A_x\) だけ変化します。これは \(S_l\) に対する「区間加算」に相当します。
もし愚直に毎回 \(S_l\) を更新して最小値を求めると、1回のクエリに \(O(N)\) かかり、全体で \(O(QN)\) となって実行時間制限に間に合いません（TLE）。 この「固定されたキー \(P_l\) に対する条件 \(P_l \ge X\)」と「動的に変化する値 \(S_l\) の区間加算・最小値取得」を効率的に処理するために、平方分割（Square Root Decomposition）を適用します。
アルゴリズム
\(M\) 個の選び方をサイズ \(B\) のバケット（グループ）に分割します。バケットの個数は \(D = \lceil M / B \rceil\) 個になります。
1. 初期化
各バケット内で、要素を \(P_l\) の昇順にソートします。
- ソートされたインデックスを sorted_l、対応する駐車スペース数を sorted_P とします。
- さらに、ソートされた順における \(S_l\) の「後ろからの累積最小値（suffix minimum）」を保持する配列 suffix_min を構築します。
- suffix_min[i] = \(\min_{j \ge i} S_{\text{sorted\_l}[j]}\)
- これにより、あるバケットにおいて \(P_l \ge X\) となる最小のインデックス \(idx\) を二分探索で見つければ、そのバケット内での条件を満たす \(S_l\) の最小値は suffix_min[idx] として \(O(1)\) で得られます。
2. 賃料の変更クエリ（\(T_j = 1\)）
区画 \(x\) の賃料が \(y\) に変更されたとき、差分 \(d = y - A_x\) を計算します。
影響を受ける \(S_l\) の範囲は連続する区間 \([QL, QR] = [\max(0, x-K), \min(M-1, x-1)]\) (0-indexed) です。
平方分割の一般的な区間更新と同様に処理します。
- 完全に含まれるバケット: バケット全体の加算値を表す変数 add[bid] に \(d\) を加算します。
- 一部だけ含まれるバケット（端のバケット）:
- 範囲内の要素 \(l\) に対して、個別に \(S_l \leftarrow S_l + d\) と更新します。
- その後、そのバケットの suffix_min を再構築（rebuild）します。\(P_l\) の順序は変わらないため、ソートし直す必要はなく、累積最小値の再計算だけで済むため \(O(B)\) で行えます。
3. 質問クエリ（\(T_j = 2\)）
すべてのバケット（\(D\) 個）に対して以下を行います。
- バケットの sorted_P において、値が \(X\) 以上となる最小のインデックス \(idx\) を二分探索（bisect_left）で求めます。
- \(idx\) がバケットのサイズ未満であれば、そのバケット内での最小値 suffix_min[idx] + add[bid] を候補とし、全体の最小値を更新します。
- すべてのバケットを探索し終えたときの最小値が答えとなります。一度も候補が見つからなかった場合は IMPOSSIBLE を出力します。
計算量
バケットサイズを \(B \approx \sqrt{M}\) とします。
- 時間計算量: \(O(M \log M + Q \sqrt{M} \log M)\)
- 初期化: \(D\) 個のバケットでそれぞれサイズ \(B\) のソートを行うため、全体で \(O(D \cdot B \log B) = O(M \log B)\) です。
- 賃料の変更クエリ: 完全に含まれるバケットの更新に \(O(D)\)、端のバケットの更新と再構築に \(O(B)\) かかるため、1クエリあたり \(O(D + B) = O(\frac{M}{B} + B)\) です。
- 質問クエリ: \(D\) 個のバケットそれぞれで二分探索を行うため、1クエリあたり \(O(D \log B) = O(\frac{M}{B} \log B)\) です。
- \(B \approx \sqrt{M}\) と調整することで、各クエリを約 \(O(\sqrt{M} \log M)\) で高速に処理できます。
- 空間計算量: \(O(N + Q)\)
- 元の配列やバケットごとの情報を保持するために必要なメモリは、要素数 \(N\) およびクエリ数 \(Q\) に対して線形です。
実装のポイント
バケットサイズ \(B\) の選定:
- 理論上は \(B = \sqrt{M}\) 付近が最適ですが、Pythonのオーバーヘッドを考慮すると \(B = 500\) 程度に固定して設定することで、二分探索の回数（バケット数 \(D\)）と再構築のコスト（バケットサイズ \(B\)）のバランスが最も良く取れ、高速に動作します。
再構築（
rebuild）の高速化:端のバケットを更新する際、バケット内のソート順（
sorted_l）は変わりません。そのため、ソート処理を完全にスキップし、累積最小値の配列suffix_minのみを後ろから走査して更新することで、定数倍を大幅に削減しています。ソースコード
import bisect
import sys
def solve():
input = sys.stdin.read
data = input().split()
if not data:
return
N = int(data[0])
K = int(data[1])
Q = int(data[2])
A = [0] + [int(x) for x in data[3 : 3 + N]]
C = [0] + [int(x) for x in data[3 + N : 3 + 2 * N]]
queries = []
idx = 3 + 2 * N
for _ in range(Q):
t = int(data[idx])
x = int(data[idx + 1])
y = int(data[idx + 2])
queries.append((t, x, y))
idx += 3
pref_C = [0] * (N + 1)
for i in range(1, N + 1):
pref_C[i] = pref_C[i - 1] + C[i]
pref_A = [0] * (N + 1)
for i in range(1, N + 1):
pref_A[i] = pref_A[i - 1] + A[i]
M = N - K + 1
P = [0] * M
S = [0] * M
for l in range(M):
P[l] = pref_C[l + K] - pref_C[l]
S[l] = pref_A[l + K] - pref_A[l]
B = 500
num_buckets = (M + B - 1) // B
bucket_start = [i * B for i in range(num_buckets)]
bucket_end = [min(M, (i + 1) * B) for i in range(num_buckets)]
sorted_l = [[] for _ in range(num_buckets)]
sorted_P = [[] for _ in range(num_buckets)]
suffix_min = [[] for _ in range(num_buckets)]
add = [0] * num_buckets
for bid in range(num_buckets):
start = bucket_start[bid]
end = bucket_end[bid]
l_list = list(range(start, end))
l_list.sort(key=lambda l: P[l])
sorted_l[bid] = l_list
sorted_P[bid] = [P[l] for l in l_list]
sz = end - start
s_min = [0] * sz
if sz > 0:
s_min[-1] = S[l_list[-1]]
for i in range(sz - 2, -1, -1):
val = S[l_list[i]]
nxt = s_min[i + 1]
s_min[i] = val if val < nxt else nxt
suffix_min[bid] = s_min
INF = 10**18
def rebuild(bid, sorted_l_bid, suffix_min_bid, S):
sz = len(sorted_l_bid)
if sz > 0:
suffix_min_bid[-1] = S[sorted_l_bid[-1]]
for i in range(sz - 2, -1, -1):
val = S[sorted_l_bid[i]]
nxt = suffix_min_bid[i + 1]
suffix_min_bid[i] = val if val < nxt else nxt
out = []
bisect_left = bisect.bisect_left
for t, x, y in queries:
if t == 1:
d = y - A[x]
A[x] = y
QL = max(0, x - K)
QR = min(M - 1, x - 1)
if QL <= QR:
bid_L = QL // B
bid_R = QR // B
if bid_L == bid_R:
for l in range(QL, QR + 1):
S[l] += d
rebuild(bid_L, sorted_l[bid_L], suffix_min[bid_L], S)
else:
for l in range(QL, bucket_end[bid_L]):
S[l] += d
rebuild(bid_L, sorted_l[bid_L], suffix_min[bid_L], S)
for bid in range(bid_L + 1, bid_R):
add[bid] += d
for l in range(bucket_start[bid_R], QR + 1):
S[l] += d
rebuild(bid_R, sorted_l[bid_R], suffix_min[bid_R], S)
else:
ans = INF
for bid in range(num_buckets):
s_P = sorted_P[bid]
idx = bisect_left(s_P, x)
if idx < len(s_P):
val = suffix_min[bid][idx] + add[bid]
if val < ans:
ans = val
if ans == INF:
out.append("IMPOSSIBLE")
else:
out.append(str(ans))
print("\n".join(out))
if __name__ == "__main__":
solve()
この解説は gemini-3.5-flash-thinking によって生成されました。
投稿日時:
最終更新: