CodeIQ/トグルスイッチ問題 の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• CodeIQ/トグルスイッチ問題 へ行く。

トグル問題
この問題はCodeIQで結城浩先生から出題されたトグル問題について解説しています。

-トグル問題の詳細は[[こちら>https://codeiq.jp/ace/yuki_hiroshi/q312]]
-結城浩先生のCodeIQのページは[[こちら>http://www.hyuki.com/codeiq/]]&note{codeiq-hyuki-official:[[CodeIQの問題に挑戦しよう！>http://www.hyuki.com/codeiq/]]};

-トグル問題のポイントは以下の２点
--すべてのトグルスイッチの状態を指定しなくてはいけない
--同じトグルスイッチの状態を指定してはいけない
-この状態で「トグルスイッチを変化させる最大の回数」を求めなくてはいけない

*見方を変えて [#a914035c]
-トグルスイッチの状態は、立方体として考えることができる
-例えば、トグルスイッチ3個の状態は立方体で表すことができる
#ref(立方体の図.png)
-この図だと、
--それぞれの軸に位が割り当てられており
--立方体=3軸あるので、3桁のトグルスイッチの状態を表すのにちょうど良い
-こう見立てると、トグル問題はすべての頂点を移動する問題になる
--ただし、問題になるのは送信ボタンを押す際のトグルスイッチ状態であるので、一筆書きの問題とはまた、違う

*更に見方を変えて [#vc631f7b]
-この問題、できることなら、なるべく多くのスイッチを変更したい
-1度に送信できる最大のスイッチ変化数は、トグルスイッチの個数までである。
--先の例で言えば3トグル、問題となるのは10トグルである
-トグルスイッチ3個の場合で言えば、1例としてこの状態の遷移が1回に得られる最大である
 000 <- -> 111
-この例では3トグル、1回の送信で得られる
-同様に、トグルスイッチの状態は、それぞれ真逆の状態とも言うべき、すべてのスイッチのオン／オフを切り替えたペアが存在する
 000 <- -> 111
 001 <- -> 110
 010 <- -> 101
 011 <- -> 100
-少なくとも、「最大」を目標とするならば、ここに示した経路は通らなくては行けない
-その上で、
--このペア間をつなぐトグルコストが最大になる
--同じ経路を2度通らないことが保証される
-アルゴリズムを考えなくてはならない
-前述したように、3トグル変化する場合は、同じ状態に戻るだけなので、前述のペア間のコストは1少ない2トグルで変化しなくてはならない。
-例題に書かれている様に、下記の様に遷移すると、3→2→3→2…の遷移の組み合わせで移動できるのが確認できる。

*最大の変化のために最小の変化を考える [#xb198363]
-なんとなく見えてきたと思うけれど、前述の遷移図を見るに、左側の最上位はすべて0、右側はすべて1になっている。
-なので、左側に並んでる数値の配列が、トグルスイッチ1個の差分だけで表現できれば、必ず最大のトグル値が得られる。