0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

公式解説に載っていなかったので。多分邪道で、公式解説の方が普通に筋がいいと思います。

問題

概要

  • $T$件のテストケースについて、以下の問題を解け。
    • 正整数$A,B$が与えられる
    • 非負整数$X,Y$で、$B+Y$が$A+X$の倍数となるようなものについて、 $X+Y$の最小値を求めよ。

制約

  • $1 \leq T \leq 100$,
  • $1 \leq A, B \leq 10^9$.

解説

まずは $A \geq B$の場合について。これは簡単で、$B$が$A$に等しくなるように$Y=A-B$とし、$X=0$としたときが$X+Y$が最小になる。ほとんど自明だが、$X > 0$と仮定すると $A \geq B$より $A+X > B$. このとき、$Y$を最小にするには $A+X=B+Y$として1倍の倍数にするほかないが、この時$Y=A+X-B$となり明らかに当初の$X=0$としたときの$Y=A-B$よりも大きくなってしまう。そのため、単に$A-B$を出力すればよい。

難しいのは $A < B$のとき。この問題を解く上で許容される計算量について考えてみると、$1 \leq T \leq 100$の条件から、1テストケースあたり最大で$O(10^7)$程度が求められる1。したがって、$O(A)$や$O(B)$の解法は許容されない。

Aが100000以下のとき

一旦計算量を無視して愚直な解法について考えてみる。
最も簡単な解法は、$X$を固定すれば$B+Y$が$A+X$の倍数になるような最小の$Y$は簡単に求めることができる2ので、$X$を全探索することだろう。$X$をどの範囲で探索すればよいかについてだが、$X=0$のとき、最小の$Y$は $(A-B \mathrm{mod} A)
\mathrm{mod} A$で求めることができる。これは明らかに$A$で上から押さえることができるので、$X+Y$の最小値は最大でも$A-1$であることがわかる。したがって、$X$について$0$から$A-1$までの範囲を全探索すれば、$X+Y$の最小値を$O(A)$で計算できる。
この方法では$A$が大きいときに対応できないので無意味に思えるが、少なくとも$A \leq 10^5$のような範囲では、明らかに有効といえる。つまり、$10^5 \leq A$ のときに他の方法で高速に$X+Y$の最小値を求めることができればよい。

Aが100000より大きいとき

この場合には、先ほどの$X$で全探索する方法は使えない。$O(A)$の解法は計算量が大きくなりすぎてしまうからである。ここで、前提条件から$A < B$であり、なおかつ$B \leq 10^9$であることを思い出そう。ここからわかることは$B/A$が最大でも$O(10^4)$くらいで収まるということである。改めてこの場合で$X=0$を仮定する。この時、$B+Y$が$A$の倍数になるということだから、ある正の整数$r$を用いて、$B+Y=rA$と書ける。式変形をすると $Y=rA-B$となり、この時$Y$を最小にしたいのだから$r$は$rA-B$が$0$以上となるような最小の$r$を選ぶのが妥当である。これはまさに$B/A$とオーダーが等しいわけで、$r$はどれだけ大きくても$O(10^4)$で押さえられることになる。
したがって、各$r$について$X+Y$の最小値を$O(1)$で求められるなら、$r$の全探索が間に合うことになる。
実際、以下の議論から、$r$を決め打ちしたときの最も$X+Y$を小さくするような$X$と$Y$を$O(1)$で求めることができる。
$r$を決め打ちしたとき、$Y+B$が$X+A$の倍数になるという条件から、以下の等式が成り立つ。

Y+B = r(A+X).

これを$Y$について解くと$Y=rA+rX-B$となる。ここで$Y$が非負という条件から$rA+rX-B \geq 0$が成り立つ必要がある。これを$X$について解くと、$X \geq (B-rA)/r$となる。ここでさらに$Y=rA+rX-B$について考えると、$Y$は$X$の一次関数になっており、その傾きは正だから、$Y$は$X$について単調増加する。したがって、$X$がとりうる最小の時に$Y$も最小となり、このときが$X+Y$も最小となる。したがって、$X$の最小値を求めれば、$r$を決め打ちしたときの$X+Y$の最小値もわかることになる。
$X \geq (B-rA)/r$は、$B-rA < 0 $のときに$X$が非負の条件から$X=0$とするのが最適であることに注意すれば、各$r$について$X+Y$の最小値を$O(1)$で求められる。したがって、$r$について全探索すれば$r$は最大で$O(10^4)$程度だから十分高速に$(X+Y)$の最小値を求められる。

結論

$A$が$10^5$くらいよりも小さいか大きいかで場合分けをする。

  • 小さいなら$X=0$のときの$X+Y$が$A$で押さえられることに注目して、$X$について$0$から$A-1$の範囲で全探索を行う
  • 大きいなら、$B/A$が最大でも$O(10^4)$程度で押さえられることに注目し、$B+Y$が$A+X$の$r$倍になるとして$r$について全探索を行う

提出コード

注釈

  1. $O(10^9)$程度の計算量が許容されると仮定して。

  2. $X$を決め打つと$A+X$の方が一意に定まる。このとき $B+Y$が$A+X$の倍数になるような最小の$Y$は、$(A+X-B\mathrm{mod}(A+X)) \mathrm{mod} (A+X)$で求めることができる。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?