AtCoder Beginner Contest 165 A問題「We Love Golf 」解説(Python3,C++,Java)

Ruteです。

AtCoder Beginner Contest 165 A問題「We Love Golf」の解説を行います。

問題URL:
https://atcoder.jp/contests/abc165/tasks/abc165_a

問題概要

(問題文を簡潔に表すと以下の通りです)
$A$以上$B$以下の整数の中に$K$の倍数が存在するかを判定せよ。
存在する場合は'OK'
存在しない場合は'NG'と出力せよ。

制約

・入力は全て整数
・$1 \leq A \leq B \leq 1000$
・$1 \leq K \leq 1000$

解法1(ループ)

この問題においてまず1つ目に思いつく解法は$(A,B)$の範囲の中に$K$の倍数が含まれているかをfor文のループで全通り調べるというものです。計算量は、$O(B)$になります。

解法2(B以下の最大のKの倍数を求める)

問題文は、$B$以下の最大の$K$の倍数が、$A$以上であるか　というように言い換えることも出来ます。よってこれを満たしているかを条件分岐で判定することでACすることも可能です。計算量は判定だけなので$O(1)$ですが制約が小さいのでこのようなことをする必要はありません。

解き方が分かりやすいのは解法1の方なので、解法1の方での解答例をこの後示します。

以下、Python3,C++,Java　それぞれの解答例です。

各言語解答例

Python3での解答例

ABC165A.py

K = int(input())
A,B = map(int,input().split())
flag = 0
#flagはフラグ関数(Kの倍数が存在したかどうか)
for i in range(A,B+1):
#(A,B)だとA以上B-1以下までを調べてしまうので注意！！
  if i%K == 0:
    flag += 1
    print("OK")
    break
if flag == 0:
  print("NG")

C++での解答例

ABC165A.cpp

#include<bits/stdc++.h>
using namespace std;
int main(){
  int k,a,b;
  cin >> k;
  cin >> a >> b;
  int flag = 0;
  for (int i = a; i <= b; i++){
    if (i%k==0){
      flag++;
      cout << "OK" << endl;
      break;
    }
  }
  if (flag == 0){
    cout << "NG" << endl;
  }
}

Javaでの解答例

ABC165A.java

import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    int k = scan.nextInt();
    int a = scan.nextInt();
    int b = scan.nextInt();
    int flag = 0;
    for (int i = a; i <=b; i++){
      if (i%k==0){
        flag++;
        System.out.println("OK");
        break;
      }
    }
    if (flag == 0){
      System.out.println("NG");
    }
  }
}