勇者を苦しめる構造3選

この問題で上位スコアを取るには、スイッチ \(k\) 種で長い道を \(O(2^k)\) 回走らせる構造が非常に重要です。
実際、公式解説生放送の \(\mathrm{26:24}\) 頃から、勇者に通路を \(O(2^k)\) 回走らせる方法が \(1\) つ解説されていました。

実は、指数関数的に通過回数を増やす方法は他にもいくつか存在します。
公式解説されていたものも含め、私がコンテスト中に考えていた方法を \(3\) つ + α、この場をお借りして紹介します。

0. そもそもなぜ指数関数的負荷が重要か

この問題における状況は、スイッチがどんな状態か、勇者がどこにいるか、の \(2\) つで決まります。
これは、勇者の行動回数の決定方法の記述からも読み取れます。

最短行動列の性質として、勇者の行動中に全く同じ状況が \(2\) 回繰り返されることは絶対にありません。
ということは、ある特定のマスに勇者がいるターン数は、最大でもスイッチの状態数である \(2^{10}\) ということになります。

盤面には高得点化に使いやすいマスも使いにくいマスも混在しています。
よって、使いやすいマスをどうやって約 \(2^{10}\) 回勇者に通過させるか、その工夫がスコアを伸ばす上で重要になります。

1. ハノイの塔移植型

（思考過程は異なりますが、最終的な形としては公式解説で扱われたものです）

ハノイの塔は、解くのに非常に手数がかかる有名な古典パズルです。
手数がかかる原理は、「\(k\) 番の板を動かすためには、最小の板と異なる棒に刺さっている板の最小番号が \(k\) であることが必要」というもの。

この発想を今回の問題に移植することができます。

「\(k\) 番目の関門を突破するには、初期状態と異なる状態にあるスイッチの最小番号が \(k\) であることが必要」と読み替えます。
関門を「スイッチの小部屋の入口を開けること」と思ってみると、以下の原理図でハノイの塔と相似な機構として動作します。

\(0\) 番目の関門であるスイッチ \(1\) の入口開放は、初期状態と異なる状態にあるスイッチの最小番号が \(0\) であるときのみ可能です。
\(1\) 番目の関門であるスイッチ \(2\) の入口開放は、初期状態と異なる状態にあるスイッチの最小番号が \(1\) であるときのみ可能です。
\(2\) 番目の関門である玉座の入口開放は、初期状態と異なる状態にあるスイッチの最小番号が \(2\) であるときのみ可能です。

この構造で、勇者はスイッチ \(0\) とスイッチ \(1\) 以降の間を \(O(2^k)\) 回走ることになります。

原理図（ビジュアライザ用データ）

入力

5 6 3
.....
.##.#
..#..
#.#.#
..#..

出力

5
0 0 3 0
1 0 3 1
0 2 3 2
1 2 3 3
1 4 3 5
3
4 0 0
0 4 1
2 4 2

実際のサイズでの例（ビジュアライザ用データ）

実際のサイズで、都合のいい壁配置だった場合の例を示します。
スイッチ \(10\) 種 \(10\) 個、使用扉 \(19\) 枚、スイッチ押下回数 \(1023\) 回、\(198613\) ターンです。

入力

20 50 10
....................
.##################.
.#................#.
.#.##############.#.
.#.#............#.#.
.#.#.##########.#.#.
.#.#.#........#.#.#.
.#.#.#.######.#.#.#.
.#.#.#.#....#.#.#.#.
.#.#.#.#.####.#.#.#.
.#.#.#.#......#.#.#.
.#.#.#.########.#.#.
.#.#.#..........#.#.
.#.#.############.#.
.#.#..............#.
.#.################.
.#..................
.###################
....................
#.#.#.#.#.#.#.#.#.#.

出力

19
1 18 1 0
0 18 1 1
1 18 3 2
0 18 3 3
1 18 5 4
0 18 5 5
1 18 7 6
0 18 7 7
1 18 9 8
0 18 9 9
1 18 11 10
0 18 11 11
1 18 13 12
0 18 13 13
1 18 15 14
0 18 15 15
1 18 17 16
0 18 17 17
0 18 19 19
10
8 11 0
19 1 1
19 3 2
19 5 3
19 7 4
19 9 5
19 11 6
19 13 7
19 15 8
19 17 9

強みと弱み

玉座から続く長い一本道を見つけさえすれば、かなり良い解がほぼ必ず作成できます。
そのため、壁配置の制約を受けにくく、安定したスコアを得るのは最も簡単だと思われます。
（解説生放送を聞いた印象では、これを上手にやるコンテストという意図で入力生成が行われていたのかもしれません）

その反面、\(O(2^k)\) 回走らせる道が玉座からの道に限られるため、盤面に対する理論値が出るようなことはあまり期待できません。

2. 10連仕分けスイッチ型

道の分岐があったとき、同じスイッチ \(2\) つと扉 \(4\) 枚で仕分けスイッチを作ることができます。
すなわち、両方の道にスイッチを \(1\) つずつ置き、その前後に扉を置き、扉の開閉を原理図のように互い違いにしておきます。
すると、この分岐に勇者がたどり着いたとき、奇数回目は道 A に、偶数回目は道 B に、強制的に進ませることができます。

これを \(k\) 個直列に繋ぎ、すべて偶数回目の通過でなければハズレ専用道にはじき出される構造にします。
すると、勇者はハズレ専用道を \(O(2^k)\) 回走ることになります。

原理図（ビジュアライザ用データ）

入力

5 6 1
.....
.###.
.....
.####
.....

出力

4
1 2 0 0
1 2 1 1
0 2 0 1
0 3 0 0
2
2 1 0
3 0 0

実際のサイズでの例（ビジュアライザ用データ）

実際のサイズで、都合のいい壁配置だった場合の例を示します。
スイッチ \(10\) 種 \(20\) 個、使用扉 \(40\) 枚、スイッチ押下回数 \(2046\) 回、\(186236\) ターンです。

入力

20 50 10
....................
.##################.
...#................
.#.#.###############
...#................
.#.################.
...#................
.#.#.###############
...#................
.#.################.
...#................
.#.#.###############
...#................
.#.################.
...#...#...#...#....
.#.#.#.#.#.#.#.#.###
...#.#.#.#.#.#.#.###
.#...#...#...#...###
.#.#.###############
....................

出力

40
0 2 0 1
0 3 0 0
1 2 0 0
1 2 1 1
0 4 0 3
0 5 0 2
1 4 0 2
1 4 1 3
0 6 0 5
0 7 0 4
1 6 0 4
1 6 1 5
0 8 0 7
0 9 0 6
1 8 0 6
1 8 1 7
0 10 0 9
0 11 0 8
1 10 0 8
1 10 1 9
0 12 0 11
0 13 0 10
1 12 0 10
1 12 1 11
0 14 0 13
0 15 0 12
1 14 0 12
1 14 1 13
0 16 0 15
0 17 0 14
1 16 0 14
1 16 1 15
1 19 2 17
1 19 3 16
0 18 2 16
0 17 2 17
1 19 4 19
1 19 5 18
0 18 4 18
0 17 4 19
20
2 1 0
3 0 0
4 1 1
5 0 1
6 1 2
7 0 2
8 1 3
9 0 3
10 1 4
11 0 4
12 1 5
13 0 5
14 1 6
15 0 6
16 1 7
17 0 7
18 2 8
19 3 8
18 4 9
19 5 9

強みと弱み

原理がシンプルで、適した地形が盤面上にあれば、最も実装が簡単だと思われます。

その反面、地形依存がかなり強く、この構造がそもそも構築不能な盤面も非常に多いです。
初期の壁配置がもっと少なくて自由に追加の壁を設置できるルールだったら、非常に強かったことでしょう。

紹介する中で唯一 \(O(2^k)\) 回の通過においてすべて同じ方向に走る構造なので、さらなるブレイクスルーで化ける可能性はあります。

3. 再帰シャトルラン型

これは、言葉だけで説明すると難しいので、先に原理図をご覧ください。

中央の部屋では左上から右下へ向かいたいのですが、ここを通過するのにスイッチ \(0\) とスイッチ \(1\) の間を \(2\) 往復する必要があります。
通過後はスイッチの状態が元通りになり、再度通過するときには再び \(2\) 往復させられます。

この構造を再帰的に設置します。
すなわち、あるシャトルラン構造のスイッチを押しに行く道に、別のシャトルラン構造を設置します。
すると、外側のシャトルランを \(1\) 回行う間に、内側のシャトルランを \(4\) 回行うことになります。
その内側シャトルラン構造のスイッチへの道にさらにシャトルラン構造を設置すると、そこは \(16\) 回行うことになります。

この再帰を \(l\) 重に設置すると、最も内側のシャトルランは \(4^{l-1}\) 回走ることになり、勇者はそのスイッチへの道を \(4^l\) 回通ることになります。
シャトルラン構造 \(1\) つにスイッチが \(2\) 種必要なので、スイッチ \(k\) 種の場合 \(O(2^k)\) 回となります。

原理図（ビジュアライザ用データ）

入力

6 6 2
....#.
###.#.
....#.
.#....
.#.###
.#....

出力

6
0 0 3 0
0 1 3 2
0 3 2 2
0 4 2 0
0 2 2 1
0 2 3 3
2
5 0 0
0 5 1

実際のサイズでの例（ビジュアライザ用データ）

実際のサイズで、都合のいい壁配置だった場合の例を示します。
スイッチ \(10\) 種 \(10\) 個、使用扉 \(30\) 枚、スイッチ押下回数 \(1364\) 回、\(161140\) ターンです。

シャトルラン構造本体を左上に強く圧縮しているため、構造がわかりづらいかもしれません。
\(2i\) 番と \(2i+1\) 番が対になっており、\(5\) 階層の再帰構造になっています。

入力

20 50 10
.#.###.###..........
.#..##..##.########.
...........#........
..##..##..##.#######
.###.###.###........
.##################.
.#..................
.#.#################
.#..................
.##################.
.#..................
.#.#################
.#..................
.##################.
.#..................
.#.#################
.#..#...#...#...#...
.##...#...#...#...#.
.###################
....................

出力

30
0 2 0 1
1 2 0 2
1 3 0 2
0 2 1 3
0 1 2 5
1 1 2 6
1 2 2 6
0 1 3 7
0 2 4 9
1 2 4 10
1 3 4 10
0 2 5 11
0 1 6 13
1 1 6 14
1 2 6 14
0 1 7 15
0 2 8 17
1 2 8 18
1 3 8 18
0 2 9 19
0 1 0 0
0 3 0 0
1 2 1 4
0 0 2 4
1 2 3 8
0 3 4 8
1 2 5 12
0 0 6 12
1 2 7 16
0 3 8 16
10
3 1 1
1 3 3
3 5 5
1 7 7
3 9 9
0 2 0
4 4 2
0 6 4
4 8 6
17 19 8

強みと弱み

長く走らせる道の終端を玉座位置と無関係に選べるため、ハノイの塔移植型ではスコアが伸びにくい配置を拾える可能性があります。

その反面、実装がかなり難しいと思われます。
また、スタート地点と玉座の間に \(1\) 回しか通らない道を用意しなければならない点もスコア面で不利です。
スタート地点と玉座がランダム配置だったら、それらが近すぎるテストケースで輝く場面もあったことでしょう。

4. 複合型

上記 \(3\) つは、組み合わせて使用できる場合があります。
例えば、以下は、スイッチ \(8\) 種 \(8\) 個をハノイの塔移植型にし、\(2\) 種 \(10\) 個でシャトルラン構造 \(5\) つを直列に繋げたものです。

スイッチ \(10\) 種 \(18\) 個、使用扉 \(37\) 枚、スイッチ押下回数 \(5355\) 回、\(190213\) ターンです。

実際のサイズでの例（ビジュアライザ用データ）

入力

20 50 10
....................
#..##..##..##..#..#.
.#.#.#.#.#.#.#.##.#.
.#.#.#.#.#.#.#.#..#.
.#.#.#.#.#.#.#.#.##.
.#.#.#.#.#.#.#.#.#..
.#.#.#.#.#.#.#.#.##.
.#.#.#.#.#.#.#.#.#..
.#.#.#.#.#.#.#.#.##.
.#.#.#.#.#.#.#.#.#..
.#.#.#.#.#.#.#.#.##.
.#.#.#.#.#.#.#.#.#..
.#.#.#.#.#.#.#.#.##.
.#.#.#.#.#.#.#.#.#..
.#.#.#.#.#.#.#.#.##.
.#.#.#.#.#.#.#.#.#..
.#.#.#.#.#.#.#.#.##.
.#.#.#.#.#.#.#.#.#..
.#.#.#.#.#.#.#.#.##.
...#...#...#...#.##.

出力

37
1 0 0 0
0 0 1 2
1 0 2 0
1 0 4 2
1 0 6 0
1 0 8 2
1 0 10 0
1 0 12 2
1 0 14 0
1 0 15 2
1 0 17 0
1 0 18 2
1 0 1 1
1 1 1 3
1 0 5 1
1 1 5 3
1 0 9 1
1 1 9 3
1 0 13 1
1 1 13 3
1 0 16 1
1 1 16 3
0 5 19 4
1 5 18 5
0 7 19 6
1 7 18 7
0 9 19 8
1 9 18 9
0 11 19 10
1 11 18 11
0 13 19 12
1 13 18 13
0 15 19 14
1 15 18 15
0 17 19 16
1 17 18 17
0 18 19 19
18
1 1 0
2 0 1
1 5 0
2 4 1
1 9 0
2 8 1
1 13 0
2 12 1
1 16 0
19 16 1
0 0 2
5 18 3
7 18 4
9 18 5
11 18 6
13 18 7
15 18 8
17 18 9

強みと弱み

例えばこの組み合わせの場合、\(1020\) 回通る道が、盤面の各所にバラバラに存在します。
つまり、一本の長い道ではなく、ムカデの足のような多数の道を何度も走らせることができます。
これは、壁が非常に入り組んで木に近くなっている今回の入力生成に対して、かなり有利に働くと思われます。

しかし、実装は非常に面倒であることが予想されます。
ただでさえ複数の構造の作成コードを書く必要があるのに、その配分なども決定しなければなりません。
短期コンテストではあまり現実的な戦略ではないかもしれません。

最後に

私は後半 \(2\) 時間、AIにおんぶに抱っこで \(8\) 種ハノイ + 直列シャトルラン複合型を目指そうとしましたが、結局ハノイの塔移植型の実装まででタイムアップでした。
それでも、同じハノイの塔移植型の方が多い中で \(6\) 位という順位を得られたのは、これだけの考察から得られたものがいい影響を生んだのかもしれません。

そして、コンテスト後も数日粘ってみましたが、結局複合型のコードは完成させられませんでした。
どなたか実装力のある方が、私の骨を拾ってくださると嬉しく思います。