AtCoderログ：0075 - ABC 085 C

# 問題

https://atcoder.jp/contests/abc085/tasks/abc085_c

## 問題文
> 日本でよく使われる紙幣は、$10000$ 円札、$5000$ 円札、$1000$ 円札です。以下、「お札」とはこれらのみを指します。
> 青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が $N$ 枚入っていて、合計で $Y$ 円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。

## 制約
> ・$1 \le N \le 2000$
> ・$1000 \le Y \le 2 \times 10^7$
> ・$N$ は整数である。
> ・$Y$ は $1000$ の倍数である。

## 収録されている問題セット
- [AtCoder に登録したら次にやること](https://qiita.com/drken/items/fd4e5e3630d0f5859067) ([第08問](https://qiita.com/drken/items/fd4e5e3630d0f5859067#%E7%AC%AC-8-%E5%95%8F--abc-085-c---otoshidama-300-%E7%82%B9))
- [AtCoder Beginners Selection](https://atcoder.jp/contests/abs)

# 回答
## 回答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$ 回程度です)。

```C++:abc085c-1.cpp
#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 となりました。

```C++:abc085c-2.cpp
#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 の値を求めることができます。具体的には

```math
\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$ 回程度のとても高速な実装となっています。

```C++:abc085c-3.cpp
#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)$ となっています。 

```C++:abc085c-4.cpp
#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 に登録したら次にやること](https://qiita.com/drken/items/fd4e5e3630d0f5859067#%E7%AC%AC-8-%E5%95%8F--abc-085-c---otoshidama-300-%E7%82%B9)
回答1と回答2が紹介されていました。

## [AtCoder の解説](https://atcoder.jp/contests/abc085/tasks/abc085_c/editorial) → [ユーザ解説](https://blog.hamayanhamayan.com/entry/2018/01/07/224854)
回答2と同じ方針でした。

## [AtCoder の解説](https://atcoder.jp/contests/abc085/tasks/abc085_b/editorial) → [コンテスト全体の解説](https://img.atcoder.jp/abc085/editorial.pdf)
方針2と同じでした。なお、解説で「$O(N)$ 時間や $O(1)$ 時間の解法も考えられます」とありますが、回答 3 は $O(N)$ 時間の解法、回答 4 は $O(1)$ 時間の解法になっています。

# リンク
## 前後の記事
- 前の記事 → [AtCoderログ：0074 - 「AtCoder Problems: Boot camp for Beginners (Easy)」のまとめ](https://qiita.com/RoadLynton/items/5e28166031894a12b6ca)