AtCoderログ：0037 - ABC 105 B

問題

問題文

ABC 洋菓子店では, $1$ 個 $4$ ドルのケーキと $1$ 個 $7$ ドルのドーナツが売られている.
このとき, 合計金額が $N$ ドルとなる買い方はあるか, 判定せよ. ただし, 同じ商品を二個以上買っても良く, 買わない商品があっても良いものとする.

制約

・$N$ は $1$ 以上 $100$ 以下の整数

収録されている問題セット

• AtCoder に登録したら次にやること (第04問類題)

回答

回答1 (AC)

合計の購入金額 n に対し、購入できるケーキの最大個数は n/4 個、ドーナッツの最大個数は n/7 個です。なので、購入するケーキの個数とドーナツの個数をループで回し、合計金額が n になる組み合わせがあるかを調べます。コードは以下のようになりました。

abc105b-1.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;

  string answer = "No";
  for ( int i=0; i<=n/4; i++ ) {
    for ( int j=0; j<=n/7; j++ ) {
      if ( 4*i+7*j==n ) {
        answer = "Yes";
      }
    }
  }
  cout << answer << endl;
}

購入方法が見つかった (answer = "Yes" となった) 後でもループを回しているのはうまくないのですが、全体の繰り返し回数が少ないため、そのままにしてしました。

回答2 (AC)

ケーキを i 個買うときの残金は n-4*i なので、これが 7 で割り切れるかを調べることにより、回答1の2つ目のループを削除することができます。コードは以下のようになりました。

abc105b-2.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
 
  string answer = "No";
  for ( int i=0; i<=n/4; i++ ) {
    if ( (n-4*i)%7==0 ) {
      answer = "Yes";
      break;
    }
  }
  cout << answer << endl;
}

回答1の繰り返し回数は $\frac{N}{4} \times \frac{N}{7} = \frac{N^2}{28} = O(N^2)$ でしたが、回答2の(最大)繰り返し回数は $\frac{N}{4}=O(N)$ 回となり、計算量的には $N$ 倍の高速化になっています。

回答3 (AC)

回答 1,2 のコードに $1 \le N \le 100$ の範囲の全ての $N$ を入力すると、"No" になるのは $N = 1, 2, 3, 5, 6, 9, 10, 13, 17$ の 9 通りとなるので、これを使って判定することが可能です。コードは以下のようになり、とてもシンプルになりました。for 文による繰り返しは不要なので、計算量はコンスタント ($O(1)$) となっています。

abc105b-3.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
 
  if ( n==1 || n==2 || n==3 || n==5 || n==6 || n==9 || n==10 || n==13 || n==17 ) {
    cout << "No" << endl;
  } else {
    cout << "Yes" << endl;
  }
}

$N$ の上限がない (つまり $N>100$ の) 場合でも、購入することができない金額は上の 9 通りしかありません。これを示すには2段階に分けて考えます。

1. $N \ge 21$ の場合：$N$, $N-7$, $N-14$, $N-21$ のいずれかは 4 の倍数になる (例えば $N=54$ のとき $N-14=40$ が 4 の倍数です) ので、その金額ぴったりにケーキを買うことができます。残額は $0, 7, 14, 21$ のいずれか ($N=54$ のときは $14$ ドル) なので、残額ぴったりにドーナツを買うことができ、$N$ ドルぴったりにケーキとドーナツが購入できます。

2. $N \le 20$ の場合：回答1,2のコードを使って調べると、上の 9 通りの $N$ は購入できないことがわかります。コードを使わないで証明するには、次のような(少し数学的な)考察が必要になります。$N$ ドルぴったりでケーキとドーナツを購入したいとき、ケーキを $2N$ 個、ドーナツを $-N$ 個購入する (このことを $(2N,-N)$ と表記します) とぴったりになります。しかしドーナツの購入個数がマイナスなので、ここから別の買い方を作ります。ケーキは 1 個 4 ドル、ドーナツは 1 個 7 ドルなので、ケーキの購入個数を 7 個減らし、ドーナツの購入個数を 4 個増やしても、支払金額の合計は変わりません。つまり、$(2N,-N)$ という買い方を $(2N-7,-N+4)$ としても購入金額は $N$ ドルのままです。ここで $N$ を 4 で割った商を $q$, 余りを $r$ (つまり $N=4q+r~(0 \le r < 4)$ とおくと、$(2N,-N)$ という買い方は $(2N-7q,-N+4q)$ と変えることができます (「ケーキの購入個数を 7 個減らし、ドーナツの購入個数を 4 個増やす」操作を $q$ 回繰り返した、つまりケーキの購入個数を $7q=7 \times q$ 個減らし、ドーナツの購入個数を $4q = 4 \times q$ 個増やした)。このとき $(2N-7q,-N+4q)=(q+2r,-r)$ となります。つまり $r=0$ のとき、ケーキを $q$ 個、ドーナツを $0$ 個買えば良いことがわかります。さらにこの買い方を変化させると $(q+2r-7,-r+4)$ となります。$r=1$ のときは $(q+2r-7,-r+4)=(q-5,3)$ となるので、$q \le 4$ のときはうまく買うことができません。$q=0$ のとき $N-4q+r=1$ が得られます。同様に $N=5,9,13,17$ が得られます。$r=2$ のときは $(q+2r-7,-r+4)=(q-3,2)$ となるので、$q \le 2$ のときはうまく買うことができず、$N=2,6,10$ が得られます。$r=3$ なら $(q+2r-7,-r+4)=(q-1,1)$ となり、$q=0$ が駄目で、$N=4q+r=3$ が得られます。

以上をまとめることで、買うことができない金額として $N = 1, 2, 3, 5, 6, 9, 10, 13, 17$ の 9 通りが得られます。

調べたこと

AtCoder の解説 → ユーザの解説

回答1が紹介されていました。「無駄な処理」は省くため、関数に分けることが言及されていました。

AtCoder の解説 → コンテスト全体の解説

回答1と回答3が紹介されていました。

リンク

前後の記事

• 前の記事 → AtCoderログ：0036 - ABC 211 A