AtCoder Beginner Contest 170 B問題「Crane and Turtle」解説(Python3,C++,Java)

AtCoder Beginner Contest 170 B問題「 Crane and Turtle 」の解説を行います。

問題URL :
https://atcoder.jp/contests/abc170/tasks/abc170_b

#問題概要
庭に何匹かの動物がいる。
情報として、
・庭の動物の総数$X$,
・足の総数$Y$
が与えられる。
鶴の足の本数は$2$本、亀の足の本数は$4$本である。

$X$,$Y$の情報にあてはまるような鶴と亀の数の組み合わせが存在するかを判定せよ。
出力：
・存在する "Yes"と出力
・存在しない "No"と出力

##制約
・ $1 \leq X \leq 100$
・ $1 \leq Y \leq 100$
・入力の全ての値は整数

#解説
##解法1(全探索)

幸い、$X$と$Y$の制約が小さいので、以下のような処理を行えばよいです。

・$X,Y$を入力
・フラグ関数$flag$を宣言し0で初期化する
・亀の匹数を$i$として、$i$を$(0,X)$の区間でとり　以下の繰返し処理を行う
　　・もし $Y - 2i $が$4$で割り切れ、かつその商が$X-i$であれ
　　　ば"Yes"と出力し、以降のループを終了する
　　　これにより組み合わせのフラグが立ったので$flag$に1を加算する
・もし$flag = 0$ならば組み合わせはないので"No"と出力する

Python3での解答例は以下のようになります。
(C++,Javaでも同様の解法で解くことができます)

Python3での解答例(解法1)

{B.py}

x,y = map(int,input().split())
flag = 0
for i in range(x+1):
  if (y - 2*i)%4 == 0 and (y -  2 * i)//4 == x - i:
    flag += 1
    print("Yes")
    break
if flag == 0:
  print("No")

※for i in range(x+1)としているのは、iの値を$(0,x)$の区間で取っているためです。 for i in range(x)とすると、iの値を$(0,x-1)$の区間でとることになります。

##解法2

鶴の匹数を$a$,亀の匹数を$b$とおくと、以下のような連立方程式が成り立つことになります。

  \begin{cases}
    a+b = X \\
    2a+4b = Y
  \end{cases}

これを解くと

  \begin{cases}
    a = \frac{4x-Y}{2}　\\
    b = \frac{-2x+Y}{2} \\
  \end{cases}

という2つの解が得られます。
この両方が整数解でかつ0より大きいかどうかを判定すればよいです。
(制約が小さいので、今回は解法1
でも余裕で実行時間制限に間に合います)

Python3での解答例(解法2)

{B2.Py}

x,y = map(int,input().split())
a = (4*x-y)/2
b = (-2*x+y)/2
if a%1 == 0 and 0 <= a and b%1 == 0 and 0 <=b:
  print("Yes")
else:
  print("No")

一般的には解法2ではなく解法1で解かれる方が多いので、ここでは解法1で解いたC++,Javaの解答例を以下に示します。

C++での解答例(解法1)

{B1.cpp}

#include<bits/stdc++.h>
using namespace std;
int main(){
  int x,y;
  cin >> x >> y;
  int flag = 0;
  for (int i = 0; i <= x; i++){
    if ((y-2*i)%4 == 0 && (y - 2 * i)/4 == x-i){
      flag++;
      cout << "Yes" << endl;
      break;
      }
    }
  if (flag == 0){
    cout << "No" << endl;
  }
}

Javaでの解答例(解法1)

{B1.cpp}

import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    int x = scan.nextInt();
    int y = scan.nextInt();
    int flag = 0;
    for (int i = 0; i <= x; i++){
      if ((y-2*i)%4 == 0 && (y - 2 * i)/4 == x-i){
        flag++;
        System.out.println("Yes");
        break;
      }
    }
    if  (flag == 0){
      System.out.println("No");
    }
  }
}