AtCoderログ：0080 - ABC 214 B

問題

問題文

$a+b+c \le S$ かつ $a \times b \times c \le T$ を満たす非負整数の組 $(a,b,c)$ はいくつありますか？

制約

・$0 \le S \le 100$
・$0 \le T \le 10000$
・$S,T$ は整数である。

回答

回答1 (AC)

非負の整数 $a,b,c$ は $a+b+c \le S \le 100$ を満たすので、$a,b,c$ の最大値は $100$ です。そこで $a,b,c$ をそれぞれ $0$ から $100$ まで変化させ、2つの条件を満たす組を数えるという、全検索の問題として解くことが出来ます。繰返し回数は $100^3=10^6$ となるので、時間内の処理が可能です。コードは以下のようになりました。

abc214b-1.cpp

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

  int answer = 0;
  for ( int a=0; a<101; a++ ) {
    for ( int b=0; b<101; b++ ) {
      for ( int c=0; c<101; c++ ) {
        if ( a+b+c<=s && a*b*c<=t ){
          answer += 1;
        }
      }
    }
  }

  cout << answer << endl;
}

回答2 (AC)

解答1のコードをちょっとだけ改良します。$a+b+c \le S$ より $a$ の最大値は $S$ であることがわかるので、a に関する for 文は a=0 から (a<101 ではなく) a<s+1 まで変化させれば十分です。$S \le 100$ なので、検索範囲が狭まっていることがわかります。

同様に、$b$ の値の最大値は $S-a$ なので、b に関する for 文は b=0 から b<s-a+1 まで変化させれば十分です。$c$ についても同様です。以上をまとめたコードは以下のようになりました。

abc214b-2.cpp

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

  int answer = 0;
  for ( int a=0; a<s+1; a++ ) {
    for ( int b=0; b<s-a+1; b++ ) {
      for ( int c=0; c<s-a-b+1; c++ ) {
        if ( a*b*c<=t ){
          answer += 1;
        }
      }
    }
  }

  cout << answer << endl;
}

調べたこと

AtCoder の解説 → 公式解説

回答2と同じ方針です。サンプルコードの8行目の「for(int b = 0; a+b <= S; b++){」という書き方を初めて知りました。

AtCoder の解説 → [ユーザ解説](https://blog.hamayanhamayan.com/entry/2021/08/15/034508

)
回答1と回答2の中間くらいの方針でした。

リンク

前後の記事

• 前の記事 → AtCoderログ：0079 - ARC 096 C