C++で解く「水とジョッキ」問題（Water Jug Problem）――最大公約数を使った計量判定アルゴリズム

容量がそれぞれ x リットルと y リットルの2つの容器（ジョッキ）があるとします。水は無限に供給されており、この2つの容器だけを使ってちょうど z リットルの水を計量できるかどうかを判定するのが、この問題の目的です。z リットルが計量可能であるためには、操作の終了時点で、どちらか一方または両方の容器内の水の合計が正確に z リットルになっている必要があります。

許容される操作

この問題では、次の3種類の操作のみが許可されています。

• どちらかの容器に水を満杯まで注ぐ。
• どちらかの容器の水をすべて捨てて空にする。
• 片方の容器からもう片方の容器へ水を移す。ただし、移し先が満杯になるか、移し元が空になるまで続けます。

具体例

例えば、x = 2、y = 5、z = 4 の場合、答えは true になります。実際、5リットルの容器を満タンにして2リットルの容器へ移す操作を繰り返すことで、最終的にちょうど4リットルを計量できます。

解法のアプローチ

この問題は、数学的な性質を利用すると非常にシンプルに解けます。手順は以下の通りです。

• x + y < z の場合：両方の容器を合わせても z リットルに届かないため、false を返します。
• x == z、y == z、または x + y == z の場合：そのまま計量できるため、true を返します。
• 上記以外の場合：z が x と y の最大公約数（gcd）で割り切れるなら true、そうでなければ false を返します。

なぜ最大公約数で判定できるのか？

この判定が成り立つ背景には、ベズーの等式（Bézout's identity）があります。これは「ax + by = z を満たす整数 a, b が存在するのは、z が gcd(x, y) の倍数であるとき、かつそのときに限る」という定理です。容器への注水・移し替え操作は、実質的に x と y を何度か足したり引いたりする操作に相当するため、z が gcd(x, y) の倍数であれば必ず計量可能になります。

C++での実装例

以下の実装を見ると、理解がより深まるでしょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool canMeasureWater(int x, int y, int z) {
      if(x + y < z) return false;
      if(x == z || y == z || x + y == z) return true;
      return z % __gcd(x, y) == 0;
   }
};
main(){
   Solution ob;
   cout << (ob.canMeasureWater(3,5,4));
}

入力

3
5
4

出力

1

出力が 1（true）となっており、3リットルと5リットルの容器で4リットルが計量可能であることが確認できます。

計算量について

この解法は、ユークリッドの互除法による gcd 計算が中心となるため、時間計算量は O(log(min(x, y))) ときわめて高速です。シミュレーションで全パターンを試す方法（BFSなど）と比べても、はるかに効率的なアプローチと言えます。