【C++】電球スイッチャー II の解き方をわかりやすく解説

問題概要

ある部屋に n 個の電球があり、すべて最初は点灯しています。壁には4つのボタンが用意されており、これらのボタンに対してちょうど m 回の操作を行ったとき、n 個の電球が取りうる状態のパターン数を求めるのがこの問題です。

電球には [1, 2, 3, ..., n] というように番号が振られており、4つのボタンの機能は以下の通りです。

• ボタン1: すべての電球の点灯・消灯を反転する
• ボタン2: 偶数番号の電球の状態を反転する
• ボタン3: 奇数番号の電球の状態を反転する
• ボタン4: (3k + 1) 番目（k = 0, 1, 2, ...）の電球の状態を反転する

例えば、n = 3、m = 1 の場合、最終的な電球の状態は次の4種類になります。

• [消灯, 点灯, 消灯]
• [点灯, 消灯, 点灯]
• [消灯, 消灯, 消灯]
• [消灯, 点灯, 点灯]

解くための考え方

一見すると複雑な組み合わせ問題に思えますが、実は以下のような数学的な性質があるため、非常にシンプルに解けます。

• 操作の順序は結果に影響しない: ボタン操作同士は互いに干渉しないため、どの順番で押しても最終的な状態は同じになります。
• 同じボタンを2回押すと元に戻る: 各操作は自己打ち消しされるため、結果を左右するのは「各ボタンを奇数回押したか、偶数回押したか」だけです。
• 最初の3個の電球の状態だけで十分: 4つのボタンの効果を組み合わせると、残りの電球の状態は自動的に決まります。そのため、答えは最大でも 2^3 = 8 パターンに収まります。

以上の性質を踏まえると、n と m の値による条件分岐だけで答えを導き出せます。

条件分岐の手順

• n が 0、または m が 0 の場合 → 1 を返す（操作できないため初期状態のみ）
• n が 1 の場合 → 2 を返す（点灯 or 消灯）
• n が 2 の場合 → m が 1 なら 3、それ以外は 4 を返す
• m が 1 の場合 → 4 を返す
• それ以外 → m が 2 なら 7、そうでなければ 8 を返す

C++での実装例

以下のコードで実際の実装を確認してみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int flipLights(int n, int m) {
      if (m == 0 || n == 0) return 1;
      if (n == 1) return 2;
      if (n == 2) return m == 1? 3:4;
      if (m == 1) return 4;
      return m == 2? 7:8;
   }
};
main(){
   Solution ob;
   cout << (ob.flipLights(3, 1));
}

入力

3
1

出力

4

まとめ

この問題は、操作の可換性と自己打ち消しの性質を見抜けるかが鍵となります。全探索のように見えて、実際には n と m の値に応じた定数個の条件分岐だけで O(1) で解答できる、数学的な洞察が活きる良い例題だと言えます。