けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 165 A - We Love Golf (7Q, 灰色, 100 点)

鹿本の例題 for文 for文:存在するかを求める K以下のAの倍数の個数 全探索 易しい全探索 全探索:線形探索法 AtCoder AtCoder100点 ABC-A 灰色diff Yes/No判定問題 易しいYes/No判定問題 スタートを0としてよい 易しい算数と数学 算数と数学 数学(整数問題) 易しい整数問題 NoviSteps7Q 整数のfor文 全探索:for文 単純化：l以上r以下のものの個数を引き算で求める

色んな解法がある！　この手の数値的なものに対して「全探索」という解法を選択肢に持てるようにしていこう。

問題概要

3 個の正の整数 K, A, B が与えられる。次の条件を満たす整数が存在するかどうかを判定せよ。

  • K の倍数である
  • A 以上 B 以下である

制約

  • 1 \le K \le 1000
  • 1 \le A \le B \le 1000

解法 (1)：for 文で全探索

A 以上 B 以下の整数の個数は B - A + 1 である。ここで、制約として 1 \le A \le B \le 1000 とあるので、たかだか 1000 通り程度しか候補がないことがわかる。

よって、全部調べても計算時間に余裕がある (このような計算時間に関する判断は、より上級の問題では常に必要になる)。

for 文を用いて、 x = A, A+1, A+2, \dots, B について、それぞれ K の倍数であるかどうかを判定すればよい。そして、 K の倍数が存在すれば "Yes" と答えればよい。

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

int main() {
    int K, A, B;
    cin >> K >> A >> B;
    
    bool exist = false;
    for (int x = A; x <= B; ++x) {
        if (x % K == 0) exist = true;
    }
    
    if (exist) cout << "OK" << endl;
    else cout << "NG" << endl;
}

解法 (2)：個数を求める

もう一つの方法は、次の定理を使うものだ！

1 以上 N 以下の整数のうち、 K の倍数は N / K 個ある ( N を K で割ったときの商)

これは、数学 IA でたびたび登場する概念だ。不安な方は数学 IA の「集合と命題」「場合の数」「整数・数学と人間の活動」といった単元を復習すると安心できると思う。

さて、そうすると次のように整理できる。

  • B 以下の K の倍数の個数は B / K 個である
  • A 未満の K の倍数の個数は (A - 1) / K 個である ( A 未満と A-1 以下は同じです)

よって、 A 以上 B 以下の整数の個数は、次のように求められる！！

B / K - (A - 1) / K

あとは、この値が 1 以上であるかどうかを判定すれば OK！！

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

int main() {
    int K, A, B;
    cin >> K >> A >> B;
    
    int num = B / K - (A - 1) / K;
    if (num >= 1)
        cout << "OK" << endl;
    else
        cout << "NG" << endl;
}