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: