Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 273 B問題 Broken Rounding

AtCoder ABC273 ABC B問題 200 pts

問題

提出解答

問題の概要

整数 $X$ が与えられる. $i=0,1,2, \dots, K-1$ の順に以下の処理を行い, 全てを終えた後の $X$ を答えよ.

$X$ を $10^i$ の位以下を四捨五入する.

制約

$0 \leq X \lt 10^{15}$
$1 \ leq K \leq 15$

解法

整数 $x$ と整数 $m$ に対して, $\operatorname{floor}(x,m), \operatorname{ceil}(x,m)$ をそれぞれ $x$ 以下で最大の $m$ の倍数, $x$ 以上で最小の整数とする.

このとき, 整数 $X$ に対して, $10^i$ の位で四捨五入した整数 $Y$ は次のようにして求められる.

$|X-\operatorname{floor}(X,10^{i+1})| \geq \operatorname{ceil}(X, 10^{i+1})$ ならば, $Y=\operatorname{ceil}(X, 10^{i+1})$
$|X-\operatorname{floor}(X,10^{i+1})| \lt \operatorname{ceil}(X, 10^{i+1})$ ならば, $Y=\operatorname{floor}(X, 10^{i+1})$

これを $i=10,1,2 \dots, K-1$ の順に計算し, 最終的な $X$ を出力すれば良い.