B - Broken Rounding Editorial by rsk0315
四捨五入の処理に関して条件分岐を陽にせずに四捨五入する方法の紹介です。
\[ \gdef\round#1#2{\mathrm{round}(#1, #2)} \gdef\dfloor#1#2{\mathrm{floor}(#1, #2)} \gdef\floor#1{\lfloor#1\rfloor} \gdef\Floor#1{\left\lfloor#1\right\rfloor} \gdef\ceil#1{\lceil#1\rceil} \gdef\Ceil#1{\left\lceil#1\right\rceil} \]
tl;dr
\(x\) を \(10^i\) の位以下を四捨五入する関数を \(\round{x}{i}\) と書くとすると、
\[ \round{x}{i} = \Floor{\frac{x+5\cdot 10^i}{10^{i+1}}}\cdot 10^{i+1} \]
が成り立つ。
また、問題全体の答えは
\[ \Floor{\frac{X+\floor{10^K/9}\cdot 5}{10^K}}\cdot 10^K \]
と書ける。
導出
簡単のため、まず \(1 = 10^0\) の位以下を四捨五入する場合を考えます。
\(10^i\) の位以下を切り捨てる関数を \(\dfloor{x}{i}\) と書くとすると、
\[ \dfloor{10a+b}{0} = \begin{cases} 10\cdot a, & \text{if}~0\le b < 10; \\ 10\cdot(a+1), & \text{if}~10\le b < 20; \\ \quad\vdots \end{cases} \]
です。これを利用し、
\[ \begin{aligned} \round{10a+b}{0} &= \begin{cases} 10\cdot a, & \text{if}~{-5}\le b < 5; \\ 10\cdot(a+1), & \text{if}~5\le b < 15; \\ \quad\vdots \end{cases} \\ &= \begin{cases} 10\cdot a, & \text{if}~0\le b+5 < 10; \\ 10\cdot(a+1), & \text{if}~10\le b+5 < 20; \\ \quad\vdots \end{cases} \\ &= \dfloor{10a+b+5}{0} \end{aligned} \]
と書けます。
ここで、\(\dfloor{x}{0} = \Floor{\frac{x}{10}}\cdot 10\) であり、多くの言語で整数型の除算で x / 10 * 10
のように書けます。
直感的な話としては、「切り捨て除算の値は、入力の値が \(10\) 変わるごとに変わる。四捨五入の際も、入力が \(10\) 変わるごとに変わるので、値を適切にずらすことで(実装が簡単な)切り捨て除算で書けるようにしたい」といった感じです。
一般の場合も同様にして、
\[ \round{x}{i} = \dfloor{x+5\cdot 10^i}{i}=\Floor{\frac{x+5\cdot 10^i}{10^{i+1}}}\cdot 10^{i+1} \]
と書けます。
関連する話
\(x\) を \(y\) で割った値の切り上げ \(\ceil{x/y}\) を (x + y - 1) / y
と書くのは比較的有名・頻出ですが、これと同じ発想です。
全体をループなしで解く話
cf. https://twitter.com/kenkenokkuu/status/1581477531277893633
\(X = a\cdot 10^K + \underbrace{44\dots 44}_{K~\text{digits}}\) のとき \(a\cdot 10^K\)、\(X = a\cdot 10^K + \underbrace{44\dots 45}_{K~\text{digits}}\) のとき \((a+1)\cdot 10^K\) となることを考えると、\(\underbrace{55\dots 55}_{K~\text{digits}}\) の下駄を履かせればよいとわかります。この値は \(\floor{10^K/9}\cdot 5\) と書けるため、
\[ \Floor{\frac{X+\floor{10^K/9}\cdot 5}{10^K}}\cdot 10^K \]
と書けます。
posted:
last update: