AtCoder Beginner Contest 231 E 問題 Minimal payments

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

ある国の通貨は $1=A_1, \dots, A_N$ 円通貨のみがある. この硬貨を使って, $X$ 円支払うとき, 支払う硬貨の枚数と, お釣りでもらう硬貨の枚数の和の最小値を求めよ.

制約

$1 \leq N \leq 60$
$1=A_1 \lt A_2 \lt \dots \lt A_N \leq 10^{18}$
$i=1,2, \dots, N-1$ に対して, $A_i$ は $A_{i+1}$ の倍数
入力はすべて整数

解法

お釣りとしてある硬貨を $t (\geq 0)$ 枚もらうということを, その硬貨を $-t$ 枚払うとみなすことにより, この問題は以下のように生着できる.

最小化: $\displaystyle \sum_{i=1}^N |t_i|$
条件
- $\displaystyle \sum_{i=1}^N t_i A_i=X$
- $t_1, t_2, \dots, t_N \in \mathbb{Z}$

この最小化問題の答えを $S(X; A_1, \dots, A_N)$ と書くことにする.

最小値を取るような $t_1, t_2, \dots, t_N \in \mathbb{Z}$ の条件を考える. まず, $A_2, A_3, \dots, A_N$ は全て $A_2$ の倍数であるから, $X-t_1 A_1=X-t_1$ は $A_2$ の倍数でなくてはならない.

そして, $|t_1| \geq A_2$ とする. このとき, $u_1, \dots, u_N$ を

$u_1=\begin{cases} t_1+A_2 & (t_1 \leq -A_2) \\ t_1-A_2 & (t_1 \geq A_2) \end{cases}, u_2=\begin{cases} t_2-1 & (t_1 \leq -A_2) \\ t_2+1 & (t_1 \geq A_2) \end{cases}, u_3=t_3, \dots, u_N=t_N$

とすると, $|u_1|+|u_2| \lt |t_1|+|t_2|$ となる. よって, $-A_2 \lt t_1 \lt A_2$ であるとしてよい.

$-A_2 \lt t_1 \lt A_2$ かつ $X-t_1 A_1=X-t_1$ が $A_2$ の倍数であるような $t_1$ は高々 $2$ つしか存在しない. $t_1=p$ が条件を満たすとき, $t_1=p$ と固定すると, 整数性を除く条件は

$\displaystyle p+\sum_{i=2}^N t_i A_i=X \iff \sum_{i=2}^N t_i \dfrac{A_i}{A_2}=\dfrac{X-p}{A_2}$

である. $\dfrac{A_2}{A_2}=1$ であるから, $t_1=p$ という追加制約の中での最小値は $|p|+S \left(\dfrac{X-p}{A_2}; 1=\dfrac{A_2}{A_2}, \dots, \dfrac{A_N}{A_2} \right)$ となることがわかった.

よって, $-A_2 \lt t_1 \lt A_2$ かつ $X-t_1 A_1=X-t_1$ を満たす整数 $t_1$ の全体の集合を $T$ とすると,

$\displaystyle \min_{t_1 \in T} \left(|t_1|+S \left(\dfrac{X-t_1}{A_2}; 1=\dfrac{A_2}{A_2}, \dots, \dfrac{A_N}{A_2} \right) \right)$

となり, 問題のサイズが小さくなった. また, $S(X;1)=|X|$ という初期条件から, 再起を用いて解くことができる.

ここで, $S(\bullet)$ の引数はたくさんあるように思えるが, 実は $X$ (第1引数) として現れるのは $i=1,2, \dots, N$ に対して, $X$ 以上の最大の整数と最小の整数に限られている. そして, $A_1, \dots$ (第2引数以降) としてはその部分の長さにのみ依存する. 以上から, 計算量は $O(N)$ であることがわかる *1.