結果
| 問題 |
No.972 選び方のスコア
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:19:12 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 342 ms / 2,000 ms |
| コード長 | 7,914 bytes |
| コンパイル時間 | 471 ms |
| コンパイル使用メモリ | 81,920 KB |
| 実行使用メモリ | 108,928 KB |
| 最終ジャッジ日時 | 2025-05-14 13:20:00 |
| 合計ジャッジ時間 | 8,756 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 32 |
ソースコード
import sys
def solve():
N = int(sys.stdin.readline())
# Handle edge case N=0 although constraints state N >= 1.
# If N=0, the list 'a' would be empty. We cannot select k>=1 elements.
# If N=1, we must select the single element. k=1. median m = a_1. score = a_1 - m = 0.
# The code should handle N=1 correctly. If N=0, it might error; let's assume N>=1.
if N == 0:
print(0)
return
A = list(map(int, sys.stdin.readline().split()))
A.sort() # Sort the array to easily find median and work with indices
# Calculate prefix sums to efficiently compute sum over ranges.
# P[i] stores the sum of A[0]...A[i-1]. P[0] = 0.
# The sum of elements A[L..R] (0-based indices) is P[R+1] - P[L].
P = [0] * (N + 1)
for i in range(N):
P[i+1] = P[i] + A[i]
max_S = 0 # Initialize maximum score found so far
# Case 1: The number of selected elements k is odd. Let k = 2j + 1.
# The median m is the element at index (k+1)/2 = j+1 in the sorted selected list.
# We iterate through each element A[p_idx] of the sorted array A and consider it as the median element.
for p_idx in range(N):
p_val = A[p_idx] # The value of the potential median element.
# To make A[p_idx] the median of k=2j+1 elements, we must select A[p_idx] itself,
# j elements less than or equal to A[p_idx], and j elements greater than or equal to A[p_idx].
# To maximize the score S = sum(b_i - m), we should select:
# - The j largest elements from A[0...p_idx-1] (these are A[p_idx-j ... p_idx-1]).
# - The j largest elements from A[p_idx+1...N-1] (these are A[N-j ... N-1]).
# This strategy requires that we have at least j elements to the left and right of A[p_idx].
# Number of elements left = p_idx. Number of elements right = N - 1 - p_idx.
# Thus, the maximum possible value for j is min(p_idx, N - 1 - p_idx).
max_j_limit = min(p_idx, N - 1 - p_idx)
optimal_j = 0 # Tracks the largest j satisfying the score increase condition. Initialized to 0 (k=1 case).
# We use binary search to find the optimal value of j. The score function S_j is concave with respect to j.
# We look for the largest j such that increasing j further improves the score.
# The condition for improvement S_j > S_{j-1} is equivalent to A[p_idx - j] + A[N - j] > 2 * p_val.
low = 0
high = max_j_limit
current_optimal_j = 0 # Store the best j found in this binary search loop. Initialized to 0.
while low <= high:
j = (low + high) // 2
if j == 0:
# j=0 corresponds to k=1. The score is always 0. This is a valid base case.
# Check if larger j values can satisfy the condition.
current_optimal_j = max(current_optimal_j, j) # Ensure 0 is considered
low = j + 1
continue
# Condition check using 0-based indices:
idx1 = p_idx - j
idx2 = N - j
# Check validity of indices (though should be guaranteed by max_j_limit)
# if idx1 < 0 or idx2 >= N: continue # Safety check
if A[idx1] + A[idx2] > 2 * p_val:
# If the condition holds, increasing j to this value improved the score.
# This j is potentially optimal, try larger j values.
current_optimal_j = max(current_optimal_j, j)
low = j + 1 # Explore larger j
else:
# If the condition does not hold, this j (and larger values) do not improve score. Search smaller j.
high = j - 1
optimal_j = current_optimal_j # The largest j that satisfies the condition.
best_j = optimal_j
# Calculate the score S for this best_j.
# S_j = sum(A[p_idx-j .. p_idx-1]) + sum(A[N-j .. N-1]) - 2*j*A[p_idx]
# Use prefix sums for range sums: sum(A[L..R]) = P[R+1] - P[L]
term1 = P[p_idx] - P[p_idx - best_j] # Sum A[p_idx-best_j .. p_idx-1]
term2 = P[N] - P[N - best_j] # Sum A[N-best_j .. N-1]
current_S = term1 + term2 - 2 * best_j * p_val
max_S = max(max_S, current_S) # Update overall maximum score
# Case 2: The number of selected elements k is even. Let k = 2j.
# The median m is the average of the two middle elements: (x_{k/2} + x_{k/2+1}) / 2 = (x_j + x_{j+1}) / 2.
# We iterate through each pair of adjacent elements (A[p_idx], A[p_idx+1]) and consider them as the median pair (x_j, x_{j+1}).
for p_idx in range(N - 1):
p_val1 = A[p_idx] # Value of the first median element candidate
p_val2 = A[p_idx+1] # Value of the second median element candidate
# To make (A[p_idx], A[p_idx+1]) the median pair of k=2j elements, we must select them,
# j-1 elements <= A[p_idx], and j-1 elements >= A[p_idx+1].
# To maximize score S = sum(b_i - m), we should select:
# - The j-1 largest elements from A[0...p_idx-1] (these are A[p_idx-(j-1) ... p_idx-1]).
# - The j-1 largest elements from A[p_idx+2...N-1] (these are A[N-(j-1) ... N-1]).
# Requires j-1 elements available left and right.
# Number of elements left of A[p_idx] is p_idx. So j-1 <= p_idx => j <= p_idx + 1.
# Number of elements right of A[p_idx+1] is N - 1 - (p_idx+1) = N - p_idx - 2. So j-1 <= N - p_idx - 2 => j <= N - p_idx - 1.
# Maximum possible j is min(p_idx + 1, N - p_idx - 1).
max_j_limit = min(p_idx + 1, N - 1 - p_idx)
# Need k=2j >= 1. Since k is even, minimal k is 2, so minimal j is 1.
if max_j_limit < 1:
continue # If max possible j is less than 1, we cannot form a pair (k>=2).
optimal_j = 1 # Default optimal j is 1 (k=2), which always gives score 0.
# Binary search for the largest j in [2, max_j_limit].
# The score S'_j is concave w.r.t. j. We look for the largest j where S'_j > S'_{j-1}.
# This condition is equivalent to A[p_idx - j + 1] + A[N - j + 1] > p_val1 + p_val2.
low = 2 # Start search from j=2, as j=1 is the base case.
high = max_j_limit
current_optimal_j = 1 # Store the best j found in this BS loop, initialized to 1.
while low <= high:
j = (low + high) // 2
# Condition check using 0-based indices:
idx1 = p_idx - j + 1
idx2 = N - j + 1
# Check validity of indices (guaranteed by range and max_j_limit logic)
# if idx1 < 0 or idx2 >= N: continue # Safety check
if A[idx1] + A[idx2] > p_val1 + p_val2:
# If condition holds, this j>=2 improved the score. Potentially optimal. Try larger j.
current_optimal_j = max(current_optimal_j, j)
low = j + 1
else:
# Condition fails, this j and larger won't improve score. Search smaller j.
high = j - 1
optimal_j = current_optimal_j # The best j found (at least 1).
best_j = optimal_j
# Calculate score S'_j for the determined best_j.
# S'_j = sum(A[p_idx-j+1 .. p_idx-1]) + A[p_idx] + A[p_idx+1] + sum(A[N-j+1 .. N-1]) - j*(A[p_idx]+A[p_idx+1])
# Use prefix sums:
term1 = P[p_idx] - P[p_idx - best_j + 1] # Sum A[p_idx-best_j+1 .. p_idx-1]
term2 = P[N] - P[N - best_j + 1] # Sum A[N-best_j+1 .. N-1]
# Note: The sums are empty if the start index exceeds the end index (e.g., when best_j=1). P[x] - P[x] = 0.
current_S = term1 + p_val1 + p_val2 + term2 - best_j * (p_val1 + p_val2)
max_S = max(max_S, current_S) # Update overall maximum score
print(max_S)
solve()