H - 展望台の配置 / Placement of Observation Decks 解説 by admin
gpt-5.5-high概要
\(N\) 個の値を好きな順番に並べ、隣接する場所からちょうど \(K\) 本の辺を選んだときの、絶対差の合計の最大値を求めます。
重要なのは、実際の並べ方を直接考えるのではなく、「各値が合計に何回プラス・マイナスで現れるか」を考えることです。
考察
まず、標高を昇順に並べたものを
\[ B_1 \leq B_2 \leq \cdots \leq B_N \]
とします。
吊り橋を 1 本選び、その両端の標高が \(x \leq y\) だとすると、加算される値は
\[ y - x \]
です。
これは、
- 大きい方の値に \(+1\)
- 小さい方の値に \(-1\)
の係数をつけたと考えることができます。
例えば、橋が \(3\) と \(10\) の間なら、寄与は
\[ 10 - 3 \]
なので、\(10\) に \(+1\)、\(3\) に \(-1\) がつきます。
選ばれた \(K\) 本の吊り橋だけを見ると、それらは一直線上の隣接辺の一部なので、各頂点の次数は高々 \(2\) です。
したがって、各値につく係数は次のいずれかです。
\[ -2, -1, 0, 1, 2 \]
また、吊り橋 1 本ごとに \(+1\) と \(-1\) が 1 つずつ発生するので、
- 正の係数の合計は \(K\)
- 負の係数の合計は \(-K\)
になります。
さらに、選ばれた辺はパスの集まりになります。辺が 1 本以上あるパスには必ず端点が 2 つあり、端点の次数は \(1\) です。
次数 \(1\) の頂点の係数は \(+1\) または \(-1\) なので、少なくとも 2 つの奇数係数が必要です。
最大化するには、
- 大きい正の係数は大きい値に
- 大きい負の係数は小さい値に
つけるのが最適です。
つまり、できるだけ
- 小さい値に \(-2\)
- 大きい値に \(+2\)
をつけたいです。
ただし、端点を作るために \(+1\) や \(-1\) も必要になります。
\(K\) が奇数の場合
\(K = 2m - 1\) とします。
正の係数の合計を \(K\) にするには、
- \(+2\) を \(m-1\) 個
- \(+1\) を \(1\) 個
使うのが最適です。
同様に負の係数は、
- \(-2\) を \(m-1\) 個
- \(-1\) を \(1\) 個
使います。
よって、
- 小さい方から \(m-1\) 個に \(-2\)
- 次の \(B_m\) に \(-1\)
- 大きい方から \(m-1\) 個に \(+2\)
- 次の \(B_{N-m+1}\) に \(+1\)
をつけます。
答えは
\[ 2 \left( \sum_{i=N-m+2}^{N} B_i - \sum_{i=1}^{m-1} B_i \right) + B_{N-m+1} - B_m \]
です。
\(K\) が偶数の場合
\(K = 2m\) とします。
単純に考えると、
- 小さい方から \(m\) 個に \(-2\)
- 大きい方から \(m\) 個に \(+2\)
をつけたくなります。
しかし、これだとすべての係数が偶数になり、パスの端点が存在しません。
そのため、どこかに \(+1\) または \(-1\) の係数を作る必要があります。
\(K\) が偶数なので、\(+1\) の個数も \(-1\) の個数も偶数個でなければなりません。
最適な候補は次の 2 通りです。
候補 1: 端点を低い側に作る
- 大きい方から \(m\) 個に \(+2\)
- 小さい方から \(m-1\) 個に \(-2\)
- \(B_m, B_{m+1}\) に \(-1\)
このときの値は
\[ S_1 = 2 \sum_{i=N-m+1}^{N} B_i - 2 \sum_{i=1}^{m-1} B_i - B_m - B_{m+1} \]
です。
候補 2: 端点を高い側に作る
- 小さい方から \(m\) 個に \(-2\)
- 大きい方から \(m-1\) 個に \(+2\)
- \(B_{N-m}, B_{N-m+1}\) に \(+1\)
このときの値は
\[ S_2 = 2 \sum_{i=N-m+2}^{N} B_i + B_{N-m} + B_{N-m+1} - 2 \sum_{i=1}^{m} B_i \]
です。
よって答えは
\[ \max(S_1, S_2) \]
になります。
これらの係数のつけ方は、低い値と高い値を交互に並べることで実際に達成できます。
例えば、端点を低い側に作る場合は
\[ 低い値 - 高い値 - 低い値 - 高い値 - \cdots - 低い値 \]
のように並べれば、内部の高い値には \(+2\)、内部の低い値には \(-2\)、両端の低い値には \(-1\) がつきます。
アルゴリズム
- 配列 \(A\) を昇順にソートし、\(B\) とする。
- \(K\) の偶奇で場合分けする。
- \(K\) が奇数なら、上の奇数の場合の式で答えを計算する。
- \(K\) が偶数なら、\(S_1, S_2\) を計算し、大きい方を答えにする。
コードでは 0-indexed で扱っているため、例えば \(B_m\) は A[m-1] に対応します。
計算量
- 時間計算量: \(O(N \log N)\)
- 空間計算量: \(O(N)\)
ソートが最も重い処理です。
実装のポイント
\(N\) が最大 \(10^6\) と大きいため、入力は高速に行う必要があります。
また、答えは最大で \(10^9 \times 10^6 = 10^{15}\) 程度になり得るので、C++ などでは long long 型が必要です。Python では整数が任意精度なのでそのまま扱えます。
ソースコード
import sys
def main():
data = sys.stdin.buffer.read()
L = len(data)
i = 0
while i < L and data[i] <= 32:
i += 1
N = 0
while i < L and data[i] > 32:
N = N * 10 + data[i] - 48
i += 1
while i < L and data[i] <= 32:
i += 1
K = 0
while i < L and data[i] > 32:
K = K * 10 + data[i] - 48
i += 1
A = [0] * N
for j in range(N):
while i < L and data[i] <= 32:
i += 1
x = 0
while i < L and data[i] > 32:
x = x * 10 + data[i] - 48
i += 1
A[j] = x
del data
A.sort()
if K & 1:
m = (K + 1) >> 1
t = m - 1
low = sum(A[:t])
high = sum(A[N - t:]) if t else 0
ans = (high - low) * 2 + A[N - m] - A[m - 1]
else:
m = K >> 1
t = m - 1
low = sum(A[:t])
high = sum(A[N - t:]) if t else 0
bottom_m = low + A[m - 1]
top_m = high + A[N - m]
ans1 = top_m * 2 - low * 2 - A[m - 1] - A[m]
ans2 = high * 2 + A[N - m - 1] + A[N - m] - bottom_m * 2
ans = ans1 if ans1 > ans2 else ans2
print(ans)
if __name__ == "__main__":
main()
この解説は gpt-5.5-high によって生成されました。
投稿日時:
最終更新: