C++で解くミラーリフレクション（鏡面反射）問題のアルゴリズムと実装

ミラーリフレクション問題とは

4つの壁すべてに鏡が張られた正方形の部屋を考えてみましょう。南西の角以外の各角には、0、1、2という番号が付けられたレシーバー（受光器）が設置されています。

この正方形の部屋の一辺の長さは p であり、南西の角から発射されたレーザー光線は、最初に東側の壁に当たります。その位置は、0番のレシーバーから距離 q の地点です。このとき、光線が最初に到達するレシーバーの番号を求めるのが本問題です。

例えば、p = 2、q = 1 の場合を考えてみます。光線は壁で反射を繰り返し、最終的に左側の壁へ戻ってきたときに初めてレシーバー2に到達します。したがって、出力は 2 となります。

解法のアプローチ

この問題は、p と q の偶奇性（パリティ）に着目することで、実際に光線の経路をシミュレートせずに効率的に解くことができます。手順は以下の通りです。

• p と q がどちらも偶数である間、次の操作を繰り返します。
  • p := p / 2
  • q := q / 2
• ループを抜けた後、p が偶数であれば 2 を返します。
• q が偶数であれば 0 を返します。
• いずれにも当てはまらない場合は 1 を返します。

なぜこの方法で正しいのか

p と q を共通因子の2で割り続けることで、両者の比 p:q を保ったまま最小の整数比に約分できます。約分後の p と q の偶奇の組み合わせにより、光線が最終的に到達する角が一意に決まるためです。

• p 偶数・q 奇数 → レシーバー 2
• p 奇数・q 偶数 → レシーバー 0
• p 奇数・q 奇数 → レシーバー 1

C++による実装例

それでは、上記のアルゴリズムをC++で実装してみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int mirrorReflection(int p, int q) {
        while(p % 2 == 0 && q % 2 == 0){
            p >>= 1;
            q >>= 1;
        }
        if(p % 2 == 0) return 2;
        if(q % 2 == 0) return 0;
        return 1;
    }
};
main(){
    Solution ob;
    cout << (ob.mirrorReflection(2, 1));
}

入力

2
1

出力

2

まとめ

ミラーリフレクション問題は、光線の反射を素朴にシミュレートすると計算量が増大しますが、p と q の偶奇性を利用すれば O(log(min(p, q))) の時間計算量で答えを求められます。ビットシフト演算（>>=）を使うことで、2での除算も効率的に行える点もポイントです。