abc-134 B Golden Appleの解法について
最近競技プログラミングをはじめて,少し勉強している。
その中で,無事ACをとれたのだが,解説を読んでいて腑に落ちない点があったので考察した。
解答
細かい内容は割愛するが,2つの整数A,Bが与えられるので,A/Bを切り上げた値を整数として出力すればよい。
解説で気になった部分は以下。
一般的に,整数A,Bに対して,A/Bの切り上げは(A+B-1)/Bの商と等しい。
たしかにこれを信じて実装すれば,(場合分けも不要となり)簡単である。
確認
例1
$A=7$, $B=3$のとき
$\frac{A}{B}$=$\frac{7}{3}$=2.3333 $\cdots$ 切り上げて3
$\frac{A+B-1}{B}$=$\frac{7+3-1}{3}$=$\frac{9}{3}$=3
となり,確かに一致する。
例2
$A=8$, $B=3$のとき
$\frac{A}{B}$=$\frac{8}{3}$=2.66666 $\cdots$ 切り上げて3
$\frac{A+B-1}{B}$=$\frac{8+3-1}{3}$=$\frac{10}{3}$=3.333$\cdots$
となり,一致しない。
というように思ってしまったのだが,結局3.3333・・・を整数型にキャストすると3となり求めたい答えと一致するということであった。
まとめ
何が言いたかったのかというと,解説中の
一般的に,整数A,Bに対して,A/Bの切り上げは(A+B-1)/Bの商と等しい。
という記述は,整数型にキャストする(される)ことで,小数点以下の切り捨て等が発生して正しい答えを得られる,ということであった。