Kazun の競プロ記録

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

AtCoder Beginner Contest 257 E問題 Addition and Multiplication 2

AtCoder ABC ABC257 E問題 500 pts

問題

提出解答

問題の概要

$N$ 円と整数 $x$ を持っている. 最初, $x=0$ である.

以下の操作を任意回できる.

$1$ 以上 $9$ 以下の整数 $i$ を1つ選び, $C_i$ 円払って, $x$ を $10x+i$ で置き換える.

$N$ 円の予算内で可能な最終的な $x$ の最大値を求めよ.

制約

$1 \leq N \leq 10^6$
$1 \leq C_i \leq N$

解法

整数の大小について, 以下が成り立つ.

相異なる2つの整数 $X,Y$ に対して, $X \gt Y$ であるための必要十分条件は以下のうちのどちらか一方が成り立つことである.

$X$ の桁数が $Y$ の桁数より真に大きい
$X$ の桁数と $Y$ の桁数が等しいとき, $X$ と $Y$ で異なるような位のうち, 最も大きい位における整数は $X$ の方が大きい.

求めるべき最大値を $\widetilde{x}$ とする. 1つ目の性質から, $\widetilde{x}$ の桁数は $N$ 円の予算内で作成可能な整数の桁数の最大値と等しく, その桁数の最大値 $d$ は

$d:=\left \lfloor \dfrac{N}{\min C} \right \rfloor$

である.

これで $\widetilde{x}$ の桁数が特定できた. このとき, $C_K=\min C$ となる整数 $K$ を一つ選び, $x$ を $K$ が $d$ 個並んだ整数とする. このとき, 次のように $x$ を変化させていくことにより, 2つ目の性質から $x=\widetilde{x}$ となる.

上の位から以下のことを行う. ただし, 各ステップ開始時点における残り予算をとする.
- $K$ より大きく, $9$ 以下の整数 $a$ のうち, $C_a \leq M$ であるような整数が存在する場合, このような整数の最大値を $A$ としたとき, 現在見ている桁の整数を $A$ に変え, 追加費用を払う.

この方法によって, 時間計算量 $O(d)=O(N)$ で求めることができる.