D - 製品の返送 / Product Return 解説 by admin
gpt-5.5-high概要
各基準値 \(K\) に対して、\(A_i < K\) となる製品を「不良品」とし、それらが作る連続区間ごとに重量最大値を足した値を求める問題です。
問い合わせを \(K\) の昇順に処理し、不良品になる製品を順に追加しながら、Union-Find で連続区間を管理します。
考察
まず、ある基準値 \(K\) を固定して考えます。
不良品は \(A_i < K\) を満たす製品です。
同じ箱に入れられるのは、元の並びで連続している不良品だけです。
例えば、不良品の位置が次のようになっているとします。
不良 不良 良品 不良 不良 不良 良品 不良
このとき、不良品の連続区間は
[1,2], [4,6], [8,8]
のように分かれます。
各連続区間について、箱をさらに分けることもできますが、分けても得にはなりません。
なぜなら、ある区間の重量最大値を \(M\) とすると、その区間全体を 1 つの箱に入れれば送料は \(M\) です。
一方、複数の箱に分けると、それぞれの箱の最大重量の和になるため、少なくとも \(M\) 以上になります。
したがって、最適な方法は
不良品の各連続区間を 1 つの箱に入れる
ことです。
よって、求める答えは
不良品が作る各連続区間について、その区間内の \(B_i\) の最大値を足したもの
になります。
素朴には、各問い合わせごとに全製品を見て、不良品の連続区間を調べれば答えを求められます。
しかしこれは \(O(NQ)\) かかり、\(N+Q \leq 2 \times 10^5\) では間に合いません。
そこで、問い合わせを基準値 \(K\) の昇順に処理します。
\(K\) が大きくなるほど、条件 \(A_i < K\) を満たす製品は増えるだけで、減ることはありません。
つまり、不良品を「追加」していく操作だけで全問い合わせを処理できます。
不良品になった位置を追加するとき、隣の位置がすでに不良品なら、連続区間がつながります。
この連続区間の管理には Union-Find が使えます。
アルゴリズム
まず、製品を \(A_i\) の昇順に並べます。
また、問い合わせも \(K_j\) の昇順に並べます。
現在処理中の基準値を \(K\) とすると、まだ追加していない製品のうち
\[ A_i < K \]
を満たすものをすべて追加します。
追加された製品を「有効」、つまり不良品として扱います。
Union-Find では、現在有効な位置同士が隣り合っていれば同じ連続区間として管理します。
各連続区間について、その区間内の重量最大値を持っておきます。
全体の答えを total とし、
\[ \text{total} = \sum \text{各連続区間の最大重量} \]
を常に保ちます。
製品 \(x\) を追加するときの変化を考えます。
まず、位置 \(x\) だけの新しい連続区間ができるので、
\[ \text{total} += B_x \]
とします。
次に、左隣 \(x-1\) がすでに不良品なら、同じ連続区間になります。
2 つの区間の最大重量をそれぞれ \(m_1, m_2\) とすると、マージ前の寄与は
\[ m_1 + m_2 \]
です。
マージ後の寄与は
\[ \max(m_1, m_2) \]
です。
したがって、total から減る量は
\[ m_1 + m_2 - \max(m_1, m_2) = \min(m_1, m_2) \]
です。
つまり、2 つの連続区間をマージするときは、小さい方の最大重量を total から引けばよいです。
右隣 \(x+1\) についても同様に処理します。
具体例で見てみます。
位置: 1 2 3 4
B: 5 2 7 3
現在、位置 \(1\) と \(3\) が不良品だとします。
不良 良品 不良 良品
連続区間は \([1]\), \([3]\) なので、
\[ \text{total} = 5 + 7 = 12 \]
です。
ここで位置 \(2\) が新たに不良品になると、
不良 不良 不良 良品
になります。
まず位置 \(2\) 単独の区間を追加して、
\[ \text{total} = 12 + 2 = 14 \]
です。
左の区間 \([1]\) とマージします。
最大重量は \(5\) と \(2\) なので、小さい方 \(2\) を引きます。
\[ \text{total} = 14 - 2 = 12 \]
次に右の区間 \([3]\) とマージします。
現在の左側の区間 \([1,2]\) の最大重量は \(5\)、右区間 \([3]\) の最大重量は \(7\) です。
小さい方 \(5\) を引きます。
\[ \text{total} = 12 - 5 = 7 \]
最終的な連続区間は \([1,2,3]\) で、最大重量は \(7\) なので正しいです。
処理の流れは次の通りです。
- 製品 \((A_i, i)\) を \(A_i\) 昇順にソートする
- 問い合わせ \((K_j, j)\) を \(K_j\) 昇順にソートする
total = 0から始める- 各問い合わせ \(K\) について、\(A_i < K\) となる未追加の製品を順に追加する
- 追加時に左右の有効な位置と Union-Find でマージする
- その時点の
totalが答え - 問い合わせは並べ替えて処理しているので、元の順番に戻して出力する
計算量
- 時間計算量: \(O((N+Q)\log(N+Q))\)
- 製品と問い合わせのソートに \(O(N\log N + Q\log Q)\)
- Union-Find の操作はほぼ \(O(1)\)
- 空間計算量: \(O(N+Q)\)
実装のポイント
Union-Find では、各連結成分について以下を管理します。
parent: 親size: Union by size 用のサイズcomp_max: その連結成分に含まれる \(B_i\) の最大値
また、ある位置がすでに不良品として追加済みかを active で管理します。
active[x] = 1
とした後、左右を確認します。
if x > 0 and active[x - 1]:
total -= unite(x, x - 1)
if x + 1 < N and active[x + 1]:
total -= unite(x, x + 1)
unite(x, y) では、2 つの連結成分をマージし、total から引くべき値、つまり
\[ \min(\text{左成分の最大重量}, \text{右成分の最大重量}) \]
を返しています。
注意点として、不良品の条件は
\[ A_i < K \]
です。
\(A_i \leq K\) ではありません。
そのため、問い合わせ処理中の追加条件は
while ip < N and items[ip][0] < k:
になります。
ソースコード
import sys
def main():
data = list(map(int, sys.stdin.buffer.read().split()))
N, Q = data[0], data[1]
B = [0] * N
items = [None] * N
p = 2
for i in range(N):
a = data[p]
b = data[p + 1]
p += 2
B[i] = b
items[i] = (a, i)
queries = [(data[p + i], i) for i in range(Q)]
items.sort()
queries.sort()
parent = list(range(N))
size = [1] * N
comp_max = B[:]
active = bytearray(N)
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def unite(x, y):
rx = find(x)
ry = find(y)
if rx == ry:
return 0
if size[rx] < size[ry]:
rx, ry = ry, rx
parent[ry] = rx
size[rx] += size[ry]
mx = comp_max[rx]
my = comp_max[ry]
if my > mx:
comp_max[rx] = my
return mx
else:
return my
ans = [0] * Q
total = 0
ip = 0
for k, qi in queries:
while ip < N and items[ip][0] < k:
x = items[ip][1]
active[x] = 1
total += B[x]
if x > 0 and active[x - 1]:
total -= unite(x, x - 1)
if x + 1 < N and active[x + 1]:
total -= unite(x, x + 1)
ip += 1
ans[qi] = total
print("\n".join(map(str, ans)))
if __name__ == "__main__":
main()
この解説は gpt-5.5-high によって生成されました。
投稿日時:
最終更新: