問題
問題文
日本でよく使われる紙幣は、$10000$ 円札、$5000$ 円札、$1000$ 円札です。以下、「お札」とはこれらのみを指します。
青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が $N$ 枚入っていて、合計で $Y$ 円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。
制約
・$1 \le N \le 2000$
・$1000 \le Y \le 2 \times 10^7$
・$N$ は整数である。
・$Y$ は $1000$ の倍数である。
収録されている問題セット
回答
回答1 (TLE)
10000円札の枚数をあらわす変数を i、5000 円札の枚数をあらわす変数を j、1000 円札の枚数をあらわす変数を k とします。最も簡単な解法は、i, j, k を 0 から n まで変化させ、条件に合うものを選び出す方法です。コードは以下のようになりました。なお設問では正解の組を1つ書き出すことが求められているので、関数を利用しました。
残念ながらこのコードは TLE となります。このコードの繰返し回数は $(N+1)^3=O(N^3)$ になっていて、$N$ は最大 $2000$ なので、繰返し回数は最大 $8 \times 10^9$ 程度となり、処理できない場合が生じてしまいます (AtCoder で AC となる計算回数は $1$ 秒あたり $10^8$ 回程度です)。
#include <bits/stdc++.h>
using namespace std;
int n;
int64_t y;
int i, j, k;
void find() {
for ( i=0; i<n+1; i++ ) {
for ( j=0; j<n+1; j++ ) {
for ( k=0; k<n+1; k++ ) {
if ( i+j+k==n && 10000*i+5000*j+1000*k==y ) {
return;
}
}
}
}
i = -1; j = -1; k = -1;
return;
}
int main() {
cin >> n >> y;
find();
cout << i << " " << j << " " << k << endl;
}
回答2 (AC)
回答1のコードを改良します。回答1のコードの問題点は三重ループを用いていることです。この三重ループを解消するために、1000 円札の枚数 k について考えます。k に関する for 文を実行する時点で変数 i と変数 j の値は決まっているので、i+j+k=n になることを利用して k の値を n-i-j に設定すると、k に関する for 文を回避することが出来ます。ただし、k の値はマイナスになる可能性があるので、マイナスの場合を排除することが必要になります。
以上の考察を用いたコードは以下のようになりました。このコードの繰返し回数は $(N+1)^2=O(N^2)$ となるので、繰返し回数は最大 $4 \times 10^6$ 程度となり、無事 AC となりました。
#include <bits/stdc++.h>
using namespace std;
int n;
int64_t y;
int i, j, k;
void find() {
for ( i=0; i<n+1; i++ ) {
for ( j=0; j<n+1; j++ ) {
k = n-i-j;
if ( k>=0 && 10000*i+5000*j+1000*k==y ) {
return;
}
}
}
i = -1; j = -1; k = -1;
return;
}
int main() {
cin >> n >> y;
find();
cout << i << " " << j << " " << k << endl;
}
回答3 (AC)
さらに回答2のコードを改良します。回答2では回答1の一番内側のループを削減したので、次は変数 j に関するループを検討します。そもそもこの設問では、変数 i, j, k は2つの条件式 i+j+k=n, 10000i+5000j+1000k=n を満たす必要があります。j に関する for 文を実行する時点で変数 i の値は決まっているので、その値をこれらの式に代入することで、j, k の値を求めることができます。具体的には
\begin{align}
j &= \frac{Y-9000i-1000N}{4000} \\
k &= N-i-j
\end{align}
となります。この式を用いると、変数 i の値から変数 j, k の値が算出されるので、これらの値が 0 以上 n 以下の整数であれば、解が求まったことになります。コードは以下のようになりました。このコードの繰返し回数は $N+1=O(N)$ となり、繰返し回数は最大 $2 \times 10^3$ 回程度のとても高速な実装となっています。
#include <bits/stdc++.h>
using namespace std;
int n;
int64_t y;
int i, j, k;
void find() {
for ( i=0; i<n+1; i++ ) {
if ( y-9000*i-1000*n>=0 && (y-9000*i-1000*n)%4000==0 ) {
j = (y-9000*i-1000*n)/4000;
} else {
continue;
}
k = n-i-j;
if ( k>=0 ) {
return;
}
}
i = -1; j = -1; k = -1;
return;
}
int main() {
cin >> n >> y;
find();
cout << i << " " << j << " " << k << endl;
}
回答4 (AC)
さらに回答3のコードを改良します。残るは変数 i に関するループの削減です。以下のような数学的(初等整数論)の考察を用いると、この設問はループなしで解を求めることが出来ます。
$Y$ 円のお年玉が $1000$ 円札だけで構成されていた場合のお札の枚数は $\frac{Y}{1000}$ 枚で、これはお年玉袋に入っているお札の最大枚数です。この状態から $1000$ 円札を $10000$ 円札と $5000$ 円札に交換することで、合計のお札の枚数を $N$ 枚にすることを考えます ($10000$ 円札と $5000$ 円札を交換したい場合には $1000$ 円札を経由することにして、直接の交換は考えないことにします)。
このとき、$1000$ 円札 $10$ 枚は $10000$ 円札 $1$ 枚と交換できます。また、$1000$ 円札 $5$ 枚は $5000$ 円札 $1$ 枚と交換できます。ここで最終的な $10000$ 円札、$5000$ 円札、$1000$ 円札の枚数を $i, j, k$ とすると、$1000$ 円札の枚数について $k = \frac{Y}{1000}-10i-5j$ となるはずです。お札の合計枚数は $N$ 枚、つまり $i+j+k=N$ なので、この式に $k$ の値を代入して $$ i+j+ \left( \frac{Y}{1000}-10i-5j \right) =N$$ つまり
$$ 9i+4j=\frac{Y}{1000}-N$$ という式を得ます。
この式は変数 $i,j$ に関する方程式ですが、変数が 2 つあるのに式は 1 つしかないので、変数 $i,j$ の値は一意には決まりません。設問のように解が 0 以上の整数という制約があってもこの状況は変わりません。しかし今回のように左辺が 2 つの変数の線型和 (変数 $i, j$ の定数倍の和) で、右辺の定数が左辺の2つの係数の最大公約数 (ここでは $4$ と $9$ の倍数の場合、変数 $i,j$ の整数解はパラメータ表示できることが知られています (今回は説明を省きます。興味をお持ちの型は「拡張ユークリッド互除法」「不定方程式の解」などをキーワードに調べてみて下さい)。
(天下りですが) $t$ を整数パラメータとするとき、$i=-4t+X$, $j=9t-2X$ は上の不定方程式の解になっています (ただし $X=\frac{Y}{1000}-N$ とおきました)。逆に、上の方程式の全ての整数解はパラメータ $t$ の値を適当に定めることで上の式で表すことが可能です。設問では $i,j$ は非負の整数なので $i \le 0$, $j \le 0$ という条件が必要で、これは $\frac{2}{9}X \le t \le \frac{1}{4}X$ と表せます。この不等式を満たす整数 $t$ が存在すれば、上記の $i,j$ は非負の整数になることが保証されます。設問では解の1つを求めれば良いので、下限値 $\frac{2}{9}X$ を切り上げて得られる整数に決め打ちすれば良いでしょう。
上記の考察を利用したコードは以下のようになります。途中で $X=\frac{Y}{1000}-N$ が正であるかと、$k=n-i-j=N-5t+X$ が正であるかのチェックをしていることに注意下さい。なおこのコードでは $N,X$ に関するループは使用していないので、計算量は $O(1)$ となっています。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
int64_t y;
cin >> n >> y;
int i = -1, j = -1, k = -1;
int64_t x = y/1000-n;
if ( x>=0 ) {
int64_t tl = (2*x+8)/9;
int64_t tr = x/4;
if ( tl<=tr && n-5*tl+x>=0 ) {
i = -4*tl+x;
j = 9*tl-2*x;
k = n-i-j;
}
}
cout << i << " " << j << " " << k << endl;
}
調べたこと
AtCoder に登録したら次にやること
回答1と回答2が紹介されていました。
AtCoder の解説 → ユーザ解説
回答2と同じ方針でした。
AtCoder の解説 → コンテスト全体の解説
方針2と同じでした。なお、解説で「$O(N)$ 時間や $O(1)$ 時間の解法も考えられます」とありますが、回答 3 は $O(N)$ 時間の解法、回答 4 は $O(1)$ 時間の解法になっています。