Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Regular Contest 138 A問題 Larger Score

AtCoder ARC ARC138 A問題 400 pts

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

長さ N の非負整数列 A の先頭 K 項の総和を \operatorname{score}(A) と書くことにする.

S:=\operatorname{score}(A) とする. A に対して, 隣接項の入れ替えを何回か行い, 操作後の整数列を A' としたとき, \operatorname{score}(A') \gt S とできるか? できる場合, その入れ替えの最小回数を求めよ.

制約

  • 2 \leq N \leq 4 \times 10^5
  • 1 \leq K \leq N-1
  • 1 \leq A_i \leq 10^9

解法

A の降順ソートを \widetilde{A} とする. このとき, \operatorname{score}(A)=\operatorname{score}(\widetilde{A}) だった場合は不可能である. また, \operatorname{score}(\widetilde{A}) が可能な最大値なので, \operatorname{score}(A) \lt \operatorname{score}(\widetilde{A}) だった場合は可能である.

可能であるとする. A の先頭 K 項に現れ, A' の先頭 K 項に現れないのが A_{i_1}, \dots, A_{i_m}, 逆に, A の先頭 K 項に現れずに, A' の先頭 K 項に現れるのが A_{j_1}, \dots, A_{j_m} であるとする ( 1 \leq i_1 \lt \dots \lt i_m \leq K \leq j_1 \lt \dots \lt j_m \leq N).

\displaystyle i \in \operatorname*{argmin}_{p=1,2, \dots, m} A_{i_p}, j \in \operatorname*{argmin}_{q=1,2, \dots, m} A_{j_q} とする. このとき, A_i \lt A_j であるから, A_i を先頭 K 項から外し, A_j を先頭 K 項に入れても目標を達成できる. これは上での段落での m=1 の場合に帰着し, 目標が厳しくなっていない.

よって, m=1 の場合のみを考えれば良い. 1 \leq i \leq K \leq j \leq N に対して, A_i \lt A_j であるとき, A_i を先頭 K 項から外し, A_j を先頭 K 項に入れるための最小回数は

  • A_i を第 K 項目に移動
  • A_j を第 (K+1) 項目に移動
  • 第 K 項目と第 (K+1) 項目を交換

で達成でき, 手数は (K-i)+(j-(K+1))+1=j-i である.

従って, 求めるべきは

\displaystyle \min_{\substack{1 \leq i \leq K \leq j \leq N \\ A_i \lt A_j}} (j-i)

である.

i=1,2, \dots, K を固定する. このとき,

\displaystyle \min_{\substack{K \leq j \leq N \\ A_i \lt A_j}} (j-i)=\left(\min_{\substack{K \leq j \leq N \\ A_i \lt A_j}} j \right)-i

であるから, A_i より大きく, 添字が最も小さいのはどこか? という問題を解くことになる.

この問題は前計算として第 K 項目以降の累積最大値を取り, 二分探索によって高速に求めることができる. なお, 最初にソートで可能不可能判定をしたが, 最初にしなくても, 可能であることと A_i \lt A_j となる 1 \leq i \leq K \leq j \leq N が存在することは同値なので, 最小値を求める仮定で可能不可能判定もできる.

以上から, 計算量 O(K \log (N-K))=O(N \log N) で求めることができた.