数値cとdを作るための最小操作回数を求めるC++コード

問題の概要

2つの数 c と d が与えられます。Amal は初期状態として、どちらも 0 である2つの数 a と b を持っており、これらに対していくつかの操作を実行したいと考えています。

各操作を実行する前に、まず正の整数 k を1つ選びます。その上で、選んだ k を用いて以下のいずれかの操作を行います。

• a と b の両方に k を加算する
• a に k を加算し、b から k を減算する
• b に k を加算し、a から k を減算する

目標は、a を c に、b を d に一致させるために必要な最小の操作回数を求めることです。到達不可能な場合は -1 を返します。

入力例

例えば、入力が c = 3、d = 5 の場合、出力は 2 になります。実際に、1回目の操作で k = 4 を選んで両方に加算すると (4, 4) となり、2回目の操作で k = 1 を選んで b に加算して a から減算すれば (3, 5) に到達できます。なお、操作の組み合わせによっては (1, 1)、(-7, 9)、(0, 2) といった中間状態も作り出すことが可能です。

解法の考え方

この問題は、各操作後に a + b の合計が常に偶数に保たれるという性質を利用すると、定数時間で解くことができます。以下の手順に従います。

if ((c ^ d) が奇数の場合):
    return -1
それ以外で c == 0 かつ d == 0 の場合:
    return 0
それ以外で c == d の場合:
    return 1
それ以外:
    return 2

それぞれのケースの意味は次の通りです。

• c ^ d(XOR)が奇数の場合: c と d の偶奇が異なることを意味します。a + b は常に偶数であるため c + d が奇数になることはなく、到達不可能なので -1 を返します。
• c = 0 かつ d = 0 の場合: 初期状態がすでに目的の状態と一致しているため、0 を返します。
• c = d の場合: k = c を選んで両方に加算するだけでよいため、1 を返します。
• それ以外の場合: 同じ偶奇を持つ異なる2つの数は、必ず2回の操作で作れるため、2 を返します。

C++実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(int c, int d){
   if ((c ^ d) & 1)
      return -1;
   else if (c == 0 && d == 0)
      return 0;
   else if (c == d)
      return 1;
   else
      return 2;
}
int main(){
   int c = 3;
   int d = 5;
   cout << solve(c, d) << endl;
}

実行結果

入力

3, 5

出力

2