【AtCoder】ARC150 B - Make Divisible

競プロ AtCoder ARC 最適化 解説AC 平方分割

解説ACした。最適化が苦手。

問題のリンク

概要

正整数 A, B が与えられるので、 B+Y が A+X の倍数になるような非負整数 X, Y の組に対し、 X+Y の最小値を求めよ。

解説
A \geq B のとき

X=0, Y=A-B, X+Y=A-B となる。(そもそも A+X \leq B+Y となる必要があるため)

A \lt B のとき

B+Y=k(A+X) であるとする。

X=B-A,Y=0,k=1 は解なので、 X+Y \leq B-A

Y \gt B-A のとき、 X+Y \gt B-A となるので、 Y \leq B-A

よって k(A+X)=B+Y \leq 2B-A なので、 k,(A+X) の少なくとも一方は \lfloor \sqrt{2B-A} \rfloor 以下である。これを全探索する。

決め打った値を t \left ( =1,2,...,\lfloor \sqrt{2B-A} \rfloor \right ) と置く。

(1) A+X=t のとき

A \gt t なら不適、そうでないとき X=t-A

このとき B+Y=kt より B+Y は t の倍数のうち B 以上の最小のもの。

よって X+Y= (t-A) + \left \lceil \frac{B}{t} \right \rceil t - B

(2) k=tのとき

t(A+X)=B+Y で、 Y \geq 0 より t(A+X) \geq B

t(A+X) \geq B となる最小の X( \geq 0) を X' としたとき、 (X,Y) = (X', t(A+X')-B) とするのが最適。

なぜなら X \lt X' のとき解にならず、 X \gt X' のとき t(A+X)-B \gt t(A+X')-B となるので、 Y がより大きくなる。

また、 X も大きくなるので X+Y も上記の解より大きくなる。

よって X+Y= X' + t(A+X')-B

以上より t を全探索して X+Y の最小値を計算すれば良い。

計算量は O ( \sqrt{B} ) となる。

感想

k,(A+X) の少なくとも一方は \lfloor \sqrt{2B-A} \rfloor 以下という部分が思いつけなかった。