エシックとヘッジは 巨大な塔の１階にいます エネルギーのバリアによって ２つめのアイテム「創造の石」から 隔てられています 手に入れるには ３つのエネルギーの流れに乗って 塔を登る必要があります 一歩前に出るやいなや 60秒のカウントダウンが始まります 部屋の奥には その中に エネルギーを保持できる― 目に見えない塔がそびえています 60秒が過ぎると エネルギーが勢いよく 上から降ってきて １ユニットずつ満たしていきます 力場によって エネルギーが前後から 漏れないようになっているのです 始まるまでの60秒の間に エシックとヘッジはどれくらいのエネルギーを 降らせるかを決めなければなりません ３回の挑戦のたびに 塔のくぼみをちょうど満たす エネルギー量を求めるのです 成功すれば エネルギーに乗って 上へと進むことができます でも量を間違えると エネルギーの昇降機は働かず 下に落ちてしまいます 壁にある図に 例が示されています この形の場合は ２ユニット分の エネルギーが入ります この形の場合は ４ユニット分― 左に３つ 右に１つです この場合も ４ユニット分です なぜなら 右端に入ったエネルギーは こぼれ出てしまうからです 降り注ぐエネルギーは 周囲に支えるものがなければ あふれてしまうのです ヘッジはブロックの列を１列ずつ可視化して 高さを測ることができますが 全体の構造を一度に 見ることはできません エシックがヘッジを どのようにプログラミングすれば それぞれの塔がくぼみに保持できる エネルギー量を把握できるでしょう？ ビデオをいったん止めて 自分で考えてみましょう ひとつの考え方は こうです それぞれの空の箱が エネルギーを保持できるのは その左方にも 右方にも 壁がある場合です その左方にも 右方にも 壁がある場合です でも これを各箱について確認すると 長い時間がかかってしまいます １列まとめて考えることは できないでしょうか？ 例えば この場合は何ユニット分 保持できるでしょう？ ［ビデオをいったん止めて 自分で考えてみましょう］ 先程の例で 問題を 分析してみましょう ブロックは５列あります 左端の列は 一番高いので エネルギーを保持できません ２列目は３ユニット分 保持できます 両側にある４段のブロックに 囲まれているからです エネルギーがいっぱいになる高さ４から ブロックの高さ１を引いて ３という答えになります ３列目も同様で 左に４段 右に４段あり 高さが３なので ４引く３で１ユニット保持できます ４列目と５列目は 右手に自分より高いものがないので エネルギーは保持できません この考え方を アルゴリズムにすることができます エネルギー量を求めたい列を基準にして ヘッジは１列ずつ見ていき 左方向で一番高い列を探し それから右方向でも 一番高い列を探します その２つの低い方が エネルギーを貯められる高さです この高さが 列自体の高さよりも高いならば そこから列の高さを差し引きます すると その答えが その列に 保持できるエネルギー量になります エネルギーを貯められる高さが 列自体の高さ以下なら エネルギーはこぼれてしまいます ヘッジはループを使って これをすべての列に適用できます 左端の列から右に向かって １列ずつ調べていくのです 列ごとに同じ手順を踏みます 左方向に一番高い列を探し 右方向に一番高い列を探し どちらか低い方から 列自体の高さを引いて その答えが正の数なら 総和にその分を加算します ヘッジはループを列の数だけ 繰り返します これで上手くいくのですが サイズが大きいと時間がかかります ヘッジは各列について左方向と右方向に たどる手順を繰り返すためです 列がN個あると N列すべてをN回参照することになります もっと速い方法はあるでしょうか？ ひとつの時間短縮法はこうです 手順を進める前に ヘッジは左端から始めて 各列に対する「左側で一番高い列」を 前もって調べておけます この場合は まず２ 最初の列のほうが高いので 再び２ それから４、４、４、と続きます それから「右側で一番高い列」も調べ 今度は右から左へ １、３、４、４、４となります 結果として メモリ上に こんな表が完成します それから ヘッジはループをもう一回りさせ さっきと同じ計算式を使い 各列に保持できるエネルギーを 計算できます 計算済みの左右の高さの 小さい方から 列自体の高さを引けばいいのです N列をN回参照する代わりに N列を３回参照するだけでよく これは線形時間です この解法をさらに最適化する方法も ありますが ここでは これで十分でしょう エシックとヘッジは 力を合わせます 最初の問題は楽勝で 塔を上へと進みます ２つめは ちょっと手強いです ３つめは 大難問で ブロックが何十列もあります 時間が刻々と過ぎますが エシックのプログラムは高速で ぎりぎりのところで ハンドルの位置を合わせます エネルギーに乗って ２人は 創造の石のありかへと導かれます 最初のアイテムの時と同じように映像が現れ 何年も前の記憶が蘇ります 世界を動かす機械が すべてを変えてしまい エシックはロボット主任技術者として 目にする現実に 不安を感じるようになりました そしてブラッドバリアが人々を 囲い込み始めたとき 何かが決定的におかしいと 気づいたのでした そこでエシックは ３つのアイテムを作り 「力」「創造性」「記憶」を 人々に取り戻させる力を付与しました そしてアイテムを３つの共同体に 隠したのです 人々にその使い方を教える前に 政府はエシックのもくろみに気づき 彼女や他のプログラマーを ロボットに逮捕させてしまいました 世界を動かす機械を使って エシックが最後に作ったのは 無知の及ぼす力から この古代の装置を守るため それを巨大な迷路に 封じ込めるロボットで そのロボットをヘッジと名付けたのです 警告もなしに エネルギーの昇降機は 突然消えてしまいました