0:00:31.587,0:00:36.438
エシックとヘッジは[br]巨大な塔の１階にいます

0:00:37.305,0:00:38.979
エネルギーのバリアによって

0:00:38.979,0:00:44.329
２つめのアイテム「創造の石」から[br]隔てられています

0:00:52.667,0:00:57.584
手に入れるには ３つのエネルギーの流れに乗って[br]塔を登る必要があります

0:00:57.584,0:01:03.523
一歩前に出るやいなや[br]60秒のカウントダウンが始まります

0:01:07.359,0:01:11.659
部屋の奥には その中に[br]エネルギーを保持できる―

0:01:11.659,0:01:14.735
目に見えない塔がそびえています

0:01:14.735,0:01:18.865
60秒が過ぎると エネルギーが勢いよく[br]上から降ってきて

0:01:18.865,0:01:21.147
１ユニットずつ満たしていきます

0:01:21.147,0:01:25.495
力場によって エネルギーが前後から[br]漏れないようになっているのです

0:01:25.495,0:01:27.817
始まるまでの60秒の間に

0:01:27.817,0:01:32.723
エシックとヘッジはどれくらいのエネルギーを[br]降らせるかを決めなければなりません

0:01:32.723,0:01:34.673
３回の挑戦のたびに

0:01:34.673,0:01:38.202
塔のくぼみをちょうど満たす[br]エネルギー量を求めるのです

0:01:38.202,0:01:42.112
成功すれば エネルギーに乗って[br]上へと進むことができます

0:01:42.112,0:01:46.653
でも量を間違えると[br]エネルギーの昇降機は働かず

0:01:46.653,0:01:48.129
下に落ちてしまいます

0:01:48.129,0:01:51.348
壁にある図に[br]例が示されています

0:01:51.348,0:01:55.618
この形の場合は ２ユニット分の[br]エネルギーが入ります

0:01:55.618,0:02:00.796
この形の場合は ４ユニット分―[br]左に３つ 右に１つです

0:02:00.796,0:02:03.421
この場合も ４ユニット分です

0:02:03.421,0:02:06.688
なぜなら 右端に入ったエネルギーは[br]こぼれ出てしまうからです

0:02:06.688,0:02:08.812
降り注ぐエネルギーは

0:02:08.812,0:02:13.538
周囲に支えるものがなければ[br]あふれてしまうのです

0:02:13.538,0:02:19.005
ヘッジはブロックの列を１列ずつ可視化して[br]高さを測ることができますが

0:02:19.005,0:02:22.808
全体の構造を一度に[br]見ることはできません

0:02:22.808,0:02:25.775
エシックがヘッジを[br]どのようにプログラミングすれば

0:02:25.775,0:02:29.591
それぞれの塔がくぼみに保持できる[br]エネルギー量を把握できるでしょう？

0:02:29.591,0:02:33.120
ビデオをいったん止めて[br]自分で考えてみましょう

0:02:38.805,0:02:41.635
ひとつの考え方は こうです

0:02:41.635,0:02:44.638
それぞれの空の箱が[br]エネルギーを保持できるのは

0:02:44.638,0:02:48.868
その左方にも 右方にも[br]壁がある場合です

0:02:48.868,0:02:51.602
その左方にも 右方にも[br]壁がある場合です

0:02:51.602,0:02:56.376
でも これを各箱について確認すると[br]長い時間がかかってしまいます

0:02:56.376,0:03:01.185
１列まとめて考えることは[br]できないでしょうか？

0:03:01.185,0:03:05.154
例えば この場合は何ユニット分[br]保持できるでしょう？

0:03:05.154,0:03:10.389
［ビデオをいったん止めて[br]自分で考えてみましょう］

0:03:10.389,0:03:13.759
先程の例で 問題を[br]分析してみましょう

0:03:13.759,0:03:15.914
ブロックは５列あります

0:03:15.914,0:03:20.484
左端の列は 一番高いので[br]エネルギーを保持できません

0:03:20.484,0:03:23.201
２列目は３ユニット分[br]保持できます

0:03:23.201,0:03:27.244
両側にある４段のブロックに[br]囲まれているからです

0:03:27.244,0:03:32.186
エネルギーがいっぱいになる高さ４から

0:03:32.186,0:03:36.449
ブロックの高さ１を引いて[br]３という答えになります

0:03:36.449,0:03:41.906
３列目も同様で 左に４段 右に４段あり[br]高さが３なので

0:03:41.906,0:03:46.537
４引く３で１ユニット保持できます

0:03:46.537,0:03:51.011
４列目と５列目は[br]右手に自分より高いものがないので

0:03:51.011,0:03:53.473
エネルギーは保持できません

0:03:53.473,0:03:57.245
この考え方を[br]アルゴリズムにすることができます

0:03:57.245,0:04:01.025
エネルギー量を求めたい列を基準にして

0:04:01.025,0:04:05.436
ヘッジは１列ずつ見ていき[br]左方向で一番高い列を探し

0:04:05.436,0:04:08.156
それから右方向でも[br]一番高い列を探します

0:04:08.156,0:04:12.957
その２つの低い方が[br]エネルギーを貯められる高さです

0:04:12.957,0:04:16.093
この高さが[br]列自体の高さよりも高いならば

0:04:16.093,0:04:18.671
そこから列の高さを差し引きます

0:04:18.671,0:04:23.634
すると その答えが その列に[br]保持できるエネルギー量になります

0:04:23.634,0:04:27.306
エネルギーを貯められる高さが[br]列自体の高さ以下なら

0:04:27.306,0:04:29.614
エネルギーはこぼれてしまいます

0:04:29.614,0:04:33.178
ヘッジはループを使って[br]これをすべての列に適用できます

0:04:33.178,0:04:38.728
左端の列から右に向かって[br]１列ずつ調べていくのです

0:04:38.728,0:04:41.431
列ごとに同じ手順を踏みます

0:04:41.431,0:04:45.547
左方向に一番高い列を探し[br]右方向に一番高い列を探し

0:04:45.547,0:04:49.622
どちらか低い方から[br]列自体の高さを引いて

0:04:49.622,0:04:53.293
その答えが正の数なら[br]総和にその分を加算します

0:04:53.293,0:04:56.988
ヘッジはループを列の数だけ[br]繰り返します

0:04:56.988,0:05:00.954
これで上手くいくのですが[br]サイズが大きいと時間がかかります

0:05:00.954,0:05:05.494
ヘッジは各列について左方向と右方向に[br]たどる手順を繰り返すためです

0:05:05.494,0:05:10.280
列がN個あると[br]N列すべてをN回参照することになります

0:05:10.280,0:05:12.260
もっと速い方法はあるでしょうか？

0:05:12.260,0:05:15.608
ひとつの時間短縮法はこうです[br]手順を進める前に

0:05:15.608,0:05:17.468
ヘッジは左端から始めて

0:05:17.468,0:05:21.420
各列に対する「左側で一番高い列」を[br]前もって調べておけます

0:05:21.420,0:05:25.215
この場合は まず２[br]最初の列のほうが高いので 再び２

0:05:25.215,0:05:27.921
それから４、４、４、と続きます

0:05:27.921,0:05:30.741
それから「右側で一番高い列」も調べ

0:05:30.741,0:05:36.960
今度は右から左へ[br]１、３、４、４、４となります

0:05:36.960,0:05:40.722
結果として メモリ上に[br]こんな表が完成します

0:05:40.722,0:05:46.143
それから ヘッジはループをもう一回りさせ[br]さっきと同じ計算式を使い

0:05:46.143,0:05:50.155
各列に保持できるエネルギーを[br]計算できます

0:05:50.155,0:05:53.662
計算済みの左右の高さの[br]小さい方から

0:05:53.662,0:05:56.789
列自体の高さを引けばいいのです

0:05:56.789,0:06:02.293
N列をN回参照する代わりに[br]N列を３回参照するだけでよく

0:06:02.293,0:06:04.707
これは線形時間です

0:06:04.707,0:06:08.034
この解法をさらに最適化する方法も[br]ありますが

0:06:08.034,0:06:10.564
ここでは これで十分でしょう

0:06:10.564,0:06:12.614
エシックとヘッジは[br]力を合わせます

0:06:14.992,0:06:19.255
最初の問題は楽勝で[br]塔を上へと進みます

0:06:21.573,0:06:23.988
２つめは ちょっと手強いです

0:06:33.051,0:06:37.051
３つめは 大難問で[br]ブロックが何十列もあります

0:06:37.051,0:06:41.367
時間が刻々と過ぎますが[br]エシックのプログラムは高速で

0:06:41.367,0:06:44.621
ぎりぎりのところで[br]ハンドルの位置を合わせます

0:06:49.015,0:06:52.781
エネルギーに乗って ２人は[br]創造の石のありかへと導かれます

0:06:55.640,0:07:01.067
最初のアイテムの時と同じように映像が現れ[br]何年も前の記憶が蘇ります

0:07:01.067,0:07:03.602
世界を動かす機械が[br]すべてを変えてしまい

0:07:03.602,0:07:06.794
エシックはロボット主任技術者として

0:07:06.794,0:07:09.223
目にする現実に[br]不安を感じるようになりました

0:07:09.223,0:07:12.067
そしてブラッドバリアが人々を[br]囲い込み始めたとき

0:07:12.067,0:07:14.665
何かが決定的におかしいと[br]気づいたのでした

0:07:14.665,0:07:16.984
そこでエシックは[br]３つのアイテムを作り

0:07:16.984,0:07:21.322
「力」「創造性」「記憶」を[br]人々に取り戻させる力を付与しました

0:07:21.322,0:07:24.243
そしてアイテムを３つの共同体に[br]隠したのです

0:07:24.243,0:07:26.541
人々にその使い方を教える前に

0:07:26.541,0:07:28.551
政府はエシックのもくろみに気づき

0:07:28.551,0:07:32.029
彼女や他のプログラマーを[br]ロボットに逮捕させてしまいました

0:07:32.029,0:07:35.295
世界を動かす機械を使って[br]エシックが最後に作ったのは

0:07:35.295,0:07:38.355
無知の及ぼす力から[br]この古代の装置を守るため

0:07:38.355,0:07:42.381
それを巨大な迷路に[br]封じ込めるロボットで

0:07:42.381,0:07:45.434
そのロボットをヘッジと名付けたのです

0:07:51.801,0:07:56.014
警告もなしに エネルギーの昇降機は[br]突然消えてしまいました