ABC085C – Otoshidama解説　Atcoder Beginners Selection解いてみた

こんにちは！seiです。

・atcoder始めてみたけど、上級者の解答は訳が分からない…
・初心者向けの解説がほしい..

この記事はAtcoder初心者の僕ができるだけ分かりやすい、今の自分のレベルに近い解答をできるだけ分かりやすく解説します！
今回は、Atcoder初心者向けの問題集「Beginners Selection」の中でも、ABC085C問題「Otoshidama」を取り上げてみました。

C++コードでの解説

解答はこちらです。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, y;
    cin >> n >> y;

    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j < n - i; j++)
        {
            int k = n - i - j;
            int total = 10000 * i + 5000 * j + 1000 * k;
            if (total == y)
            {
                cout << i << " " << j << " " << k << endl;
                return 0;
            }
        }
    }

    cout << "-1 -1 -1" << endl;
    return 0;
}

nはお札の枚数、yは合計金額です。

for (int i = 0; i <= n; i++)
{
    for (int j = 0; j < n - i; j++)
    {
        int k = n - i - j;
        int total = 10000 * i + 5000 * j + 1000 * k;
        if (total == y)
        {
            cout << i << " " << j << " " << k << endl;
            return 0;
        }
    }
}

次に、全探索を行います。forループを2つ使い、お札の枚数を全通り試します。
変数iが1万円札の枚数、jが5千円札の枚数、kが千円札の枚数です。jのループは一万円札をすでにi枚選んでいるので、ループはn-jまでで十分です。i,jが決まれば、kは確定するのでもう一度forでループする必要はありません。
一パターン見つければよいので、見つかった瞬間coutで出力してreturnで終了です！

全探索とは？

この問題は、全探索を使って解くことができます。全探索とは、その名の通りあり得る場合を「全通り」試すアルゴリズムです。
今回の場合はforが二重になっています。n*(n-i) 回なので計算量はO(n^2)ですね。N≦2*10^3なので大体10^6ほど計算が必要です。
競技プログラミングでは10^8~10^9ほどが限界なのでセーフです。

まとめ

僕は最初以下のようなコードを書いてTLEになっていました。これはO(n^3)なのでめちゃ遅いです。
今回のようにあらかじめ枚数が決まっている場合はループが削減できないか考えると良いと思います。

#include<bits/stdc++.h>
using namespace std;

void keisan(int N,int Y,int arr[3]){
    int manP,gosenP,senP,result[3];
    for (int i=N;i>=0;i--){
        manP= 10000*i;
        if(manP > Y) continue;
        for(int j=N;j>=0;j--){
            gosenP = 5000*j;
            if(manP+gosenP > Y) continue;
            for(int k=0;k<=N;k++){
                senP=1000*k;
                if(Y == manP+gosenP+senP && i+k+j == N) {
                    arr[0] =i;
                    arr[1] =j;
                    arr[2] =k;
                    return;
                };
                if(manP+gosenP+senP>Y) break;
            }
        }
    }
}

int main(){
    int N,Y,result[3] ={-1,-1,-1};
    cin >> N >> Y;

    keisan(N,Y,result);

    cout << result[0] <<" "<<result[1] <<" " <<result[2];

    return 0;
}