トグル問題
この問題はCodeIQで結城浩先生から出題されたトグル問題について解説しています。
- トグル問題のポイントは以下の2点
- すべてのトグルスイッチの状態を指定しなくてはいけない
- 同じトグルスイッチの状態を指定してはいけない
- この状態で「トグルスイッチを変化させる最大の回数」を求めなくてはいけない
見方を変えて†
- トグルスイッチの状態は、立方体として考えることができる
- 例えば、トグルスイッチ3個の状態は立方体で表すことができる
- この図だと、
- それぞれの軸に位が割り当てられており
- 立方体=3軸あるので、3桁のトグルスイッチの状態を表すのにちょうど良い
- こう見立てると、トグル問題はすべての頂点を移動する問題になる
- ただし、問題になるのは送信ボタンを押す際のトグルスイッチ状態であるので、一筆書きの問題とはまた、違う
更に見方を変えて†
最大の変化のために最小の変化を考える†
- なんとなく見えてきたと思うけれど、前述の遷移図を見るに、左側の最上位はすべて0、右側はすべて1になっている。
- なので、左側に並んでる数値の配列が、トグルスイッチ1個の差分だけで表現できれば、必ず最大のトグル値が得られる。