アジの開きを閉じる。

競プロ(AtCoder)中心のブログ

【解説】ARC138 A - Larger Score

ARC 解説

ARC138 A の公式解説がよく理解できなかった人向けの解説記事です。

執筆時レート：茶

問題文→https://atcoder.jp/contests/arc138/tasks/arc138_a

公式解説→https://atcoder.jp/contests/arc138/editorial/3746

目次

問題
制約
確認
解説
実装
補足

問題

長さ $N$ の整数列 $A = (A_1, A_2, ..., A_N)$ が与えられる。

$A$ の先頭 $K$ 項の和をスコアとし、入力で与えられた $A$ のスコアを $s$ とする。

$A$ において任意の回数だけ隣接する $2$ 要素をswapすることにより、スコアを $s+1$ 以上にすることは可能か。

可能ならば最小の操作回数を出力し、可能でないならば $-1$ を出力せよ。

f:id:Ajinoko33:20220412031737p:plain

制約

$2 \leq N \leq 4 \times 10 ^ {5}$
$1 \leq K \leq N - 1$
$1 \leq A_i \leq 10 ^ {9}$
入力される値はすべて整数

確認

$2$ 要素を入れ替えることをswapと言います。

隣接する $2$ 要素をswapする操作を適当に行うことで、他の要素の順番はそのままに、ある要素を移動させることができます。

f:id:Ajinoko33:20220412031853p:plain

解説

具体的なケースで考えてみます。

$K=3$
$A = (3, 1, 4, 1, 2, 5, 2)$

f:id:Ajinoko33:20220412031917p:plain

この場合、最適解の一つとして、次のような移動が考えられます。

赤丸の要素は、移動前後で青エリア内⇄外の移動をした要素です。

f:id:Ajinoko33:20220412031932p:plain

スコアは $8 (= 3 + 1 + 4)$ から $11 (= 2 + 4 + 5)$ に増加しており、確かに目的は達成できています。

次に、この解の操作回数について考えてみます。

赤丸の要素は青エリア内⇄外の移動をしなければなりません。

青エリア内→外で移動させる各要素をそれぞれ最小操作回数で移動させるとき、最も操作回数が必要になるのは、青エリアの境界から一番遠い位置にある要素 $3$ です。

一方、青エリア外→内の移動については、一番右にある要素 $5$ が青エリアの境界から最も遠いので、操作回数が最大です。

最適解を達成するには少なくとも、これら $2$ 要素を青エリア内外で移動させるだけの操作回数が必要になります。これら $2$ 要素だけの移動は、

要素 $3$ を青エリア内の右端に移動させる( $2$ swap)
要素 $5$ を青エリア外の左端に移動させる( $2$ swap)
青エリアの狭間でswap

とすることで、最小操作回数で達成できます。

操作回数は

(要素 $5$ のindex) - (要素 $3$ のindex) $= 6 - 1 = 5$

と、計算で求められます。

f:id:Ajinoko33:20220412031947p:plain

よって、先の最適解では他の要素も移動させなければならないので、操作回数は $5$ 以上だと分かります。

ここで、目的達成のためには、すべての要素を移動させる必要はありません。

スコアを $1$ でも大きくすれば良いのですから、

青エリア内のある $1$ 要素と、それよりも大きい、外側にある $1$ 要素を移動させる

だけで良いです。

どのような最適解を考えても、このような関係にある $2$ 要素は必ず存在します。(存在しなければスコアが増加しないため。簡単な証明は注釈に。)*1

先ほどのケースだと、例えば、 $1$ と $2$ だけを入れ替えれば良いです。

f:id:Ajinoko33:20220412031959p:plain

この場合の最小操作回数は先ほどと同様に考えて、

(要素 $2$ のindex) - (要素 $1$ のindex) $= 5 - 2 = 3$

で求められます。

これは先の最適解の操作回数の下限である $5$ 以下です。

つまり、目的達成のためには、

青エリア内のある $1$ 要素と、それよりも大きい、外側にある $1$ 要素を移動させる

だけで良いので、そのうち操作回数が最小になるものを見つければ良いです。

すなわち、 $1 \leq i \leq K, K+1 \leq j \leq N, A_i \lt A_j$ を満たす $(i, j)$ に対し、 $\min (j-i)$ を求める問題になります。

実装

$(A_i , -i)$ という要素とindexのペアを昇順に並べ、舐めていきます。

詳しい実装は公式解説を参照してください。

補足

実装において

なぜ $i$ ではなく $-i$ としてペアをつくるのか？

という疑問に対しては、次のケースで考えてみると分かると思います。

$K=2$
$A = (2, 3, 3)$

一言で言うと、「青エリア内外で等しい要素がある場合、舐めるときに青エリア外にある方を優先して舐めたいため」です。

*1:背理法による証明です。最適解において、「青エリア内→外で移動させるすべての要素 $a$ に対し、青エリア外→内で移動させる要素 $b$ のうち $a \lt b$ を満たすものが存在しない」と仮定します。青エリア内→外で移動させる要素 $a$ のうち最小のものを $m$ とします。仮定より、青エリア外→内で移動させるすべての要素 $b$ に対して、 $m \geq b$ が成立します。よってすべての $a, b$ に対し $a \geq m \geq b$ が成立します。したがって、 $\sum a \geq \sum b$ となるため、すべての $a, b$ を入れ替えてもスコアは増加しません。これは最適解であることに矛盾します。[終]