AtCoder Regular Contest 147 A問題 Max Mod Min

問題

長さ $N$ の正の整数列 $A=(A_1, \dots, A_N)$ がある.

次の操作を $A$ の長さが $1$ になるまで繰り返し行う.

$A_i=\max A, A_j=\min A$ を満たす $1$ 以上 $|A|$ 以下の整数 $i,j$ を1つ取る. その後, $A_i$ を $A_i \pmod{A_j}$ で置き換える. そして, $A_i=0$ ならば, $A$ から $A_i$ を取り除く.

このとき, 各操作において, 条件を満たすような $(i,j)$ の取り方に依らずに操作の回数は等しいことが証明できる. その操作の回数を求めよ.

整数の剰余について, 以下の事実が成り立つ.

$a$ を $b$ で割った余りを $r$ とする. このとき, $\displaystyle r \lt \frac{a}{2}$ が成り立つ.

証明

$b \leq \frac{a}{2}$ のとき, $r$ は $b$ で割った余りなので, $r \lt b \leq \frac{a}{2}$ である.
$b \gt \frac{a}{2}$ のとき, $2b \gt a$ なので, $a$ を $b$ で割った商は $1$ である. よって, 余り $r$ について, $r=a-b \lt \frac{a}{2}$ である.

よって, 各項において, 最大値として選ばれるとその項は半分以下になる. このことから, 最初に $a$ であった項が選ばれる回数は高々 $\left \lfloor \log_2 a \right \rfloor$ 回である. このことから, 答えを $X$ としたとき,

$X \leq N \log_2 (\max A)$

が成り立つ. 今, $N \leq 2 \times 10^5, \max A \leq 10^9$ であったから, $A$ にある最大値, 最小値を選ぶ操作を高速にできれば愚直なシミュレーションで計算できそうである.

では, 高速に求める方法を考える. このとき, 実は次のようにして高速にシミュレーションすることができる.

$A$ を昇順にソートし, $A$ を両側 Queue とみなす.
以下の操作をである限り繰り返す.
- $A$ の末項を dequeue し, その項を $a$ とする. また, $A$ の初項を $m$ とする (pop はしない).
- $b:=a \pmod{m}$ としたとき, $b \gt 0$ ならば, $b$ を $A$ に挿入したいが, $b \leq m$ であるから, $A$ の初項に enqueue する. $b=0$ ならば何もしない.