問題
要約
-
長さNの数列A = (A1, A2, ..., AN)が与えられる。
-
「操作」は以下の手順で行われる：
- 1 ≤ i ≤ N を満たす整数 i を選択。
- 以下の2つのうちどちらかを選んで実行
a) Ai に 1 を加算する。
b) Ai から 1 を減算する。
-
Q個の質問に答える。
-
i番目の質問
- 「操作」を0回以上何度でも使って、数列Aの全ての要素をXiにするために必要な「操作」の最小回数を求める。
- N: 数列Aの長さ
- A = (A1, A2, ..., AN): 与えられる数列
- Q: 質問の数
- Xi: i番目の質問で、数列Aの全ての要素をこの値にする
既存投稿一覧ページへのリンク
独り言
具体例
N = 5, A = [1, 3, 5, 7, 9], X = 6
累積和の計算
まず、Aの累積和CSを計算：
CS = [1, 4, 9, 16, 25]
二分探索
Xが6なので、二分探索を使ってAの中で6が入るべき位置を見つける。
この場合、インデックス2（値5）とインデックス3（値7）の間になる。
操作回数の計算
Aの要素を全て6にするために必要な操作回数を計算。
X以下の要素（1, 3, 5）に対する操作
必要な操作回数 = X * (idx + 1) - CS[idx]
= 6 * 3 - 9 = 9
Xより大きい要素（7, 9）に対する操作
必要な操作回数 = CS[N-1] - CS[idx] - X * (N - idx - 1)
= 25 - 9 - 6 * 2 = 4
合計操作回数
9 + 4 = 13
X以下の要素
これらの要素をXにするには、それぞれの要素を増やす必要がある。
全てをXにした場合の合計（6 * 3）から、現在の合計（CS[idx] = 9）を引くことで、必要な増加量（つまり操作回数）が分かる。
Xより大きい要素
これらの要素をXにするには、それぞれの要素を減らす必要がある。
現在の合計（CS[N-1] - CS[idx] = 25 - 9 = 16）から、全てをXにした場合の合計（6 * 2）を引くことで、必要な減少量が分かる。
解法手順
- 入力を受け取る（N, Q, A）。
- 数列Aをソートする。
- Aの累積和（cs）を計算する。
- 各質問に対して以下の処理を行う：
a. 目標値Xiを入力として受け取る。
b. 二分探索関数（Nibutan）を使用して、Xi以下の最大の要素のインデックス（idx）を求める。
c. idxの値に応じて、以下の3つの場合に分けて操作回数を計算する：- idx が -1 の場合（全ての要素がXiより大きい）
- idx が N の場合（全ての要素がXi以下）
- それ以外の場合（Xiより小さい要素と大きい要素が混在）
d. 計算した操作回数を結果リスト（ans）に追加する。
- 全ての質問に対する結果を出力する。
ACコード
ac.py
def Nibutan(x, n_list):
length = len(n_list)
ok = 0
ng = length - 1
if n_list[0] > x: # xが最小値より小さい場合
return -1
if n_list[-1] < x: # xが最大値より大きい場合
return length
while ng - ok > 1:
mid = (ok + ng) // 2
if n_list[mid] <= x:
ok = mid
else:
ng = mid
return ok
def io_func():
# 入力を受け取る
N, Q = map(int, input().split()) # 数列の長さNと質問の数Q
A = list(map(int, input().split())) # 数列A
return N, Q, A
def solve(N, Q, A):
A.sort() # 数列Aをソート
# 累積和を計算
cs = [0] * N
for i in range(N):
if i == 0:
cs[0] = A[0]
else:
cs[i] = cs[i-1] + A[i]
ans = []
for _ in range(Q):
X = int(input()) # 目標値X
idx = Nibutan(X, A) # 二分探索でXの位置を特定
if idx == -1: # Xが最小値より小さい場合
ans.append(cs[N-1] - X*N)
elif idx == N: # Xが最大値より大きい場合
ans.append(X*N - cs[N-1])
else: # Xが最小値と最大値の間にある場合
sum1 = -cs[idx] + X * (idx+1)
sum2 = cs[N-1] - cs[idx] - X * (N - idx - 1)
ans.append(sum1 + sum2)
# 結果を出力
for result in ans:
print(result)
# メイン処理
N, Q, A = io_func()
solve(N, Q, A)
###
# - N: 数列Aの長さ
# - Q: 質問の数
# - A: 元の数列
# - cs: 累積和を格納するリスト
# - X: 各質問での目標値
# - idx: 二分探索で求めたXの位置
# - ans: 各質問に対する答えを格納するリスト
# 1. 入力処理（io_func関数）
# - 数列の長さNと質問の数Qを受け取る
# - 数列Aの要素を受け取る
# 2. 主処理（solve関数）
# - 数列Aをソートする
# - 累積和csを計算する
# - 各質問に対して以下の処理を行う：
# a. 目標値Xを入力として受け取る
# b. 二分探索（Nibutan関数）を用いて、X以下の最大の要素のインデックスを求める
# c. 求めたインデックスを基に、3つの場合に分けて最小操作回数を計算する
# - 各質問の結果を出力する
# 3. 二分探索（Nibutan関数）
# - ソートされた数列に対して、指定された値x以下の最大の要素のインデックスを返す
# - xが最小値より小さい場合は-1を、最大値より大きい場合はリストの長さを返す