1 00:00:31,587 --> 00:00:36,438 エシックとヘッジは 巨大な塔の1階にいます 2 00:00:37,305 --> 00:00:38,979 エネルギーのバリアによって 3 00:00:38,979 --> 00:00:44,329 2つめのアイテム「創造の石」から 隔てられています 4 00:00:52,667 --> 00:00:57,584 手に入れるには 3つのエネルギーの流れに乗って 塔を登る必要があります 5 00:00:57,584 --> 00:01:03,523 一歩前に出るやいなや 60秒のカウントダウンが始まります 6 00:01:07,359 --> 00:01:11,659 部屋の奥には その中に エネルギーを保持できる― 7 00:01:11,659 --> 00:01:14,735 目に見えない塔がそびえています 8 00:01:14,735 --> 00:01:18,865 60秒が過ぎると エネルギーが勢いよく 上から降ってきて 9 00:01:18,865 --> 00:01:21,147 1ユニットずつ満たしていきます 10 00:01:21,147 --> 00:01:25,495 力場によって エネルギーが前後から 漏れないようになっているのです 11 00:01:25,495 --> 00:01:27,817 始まるまでの60秒の間に 12 00:01:27,817 --> 00:01:32,723 エシックとヘッジはどれくらいのエネルギーを 降らせるかを決めなければなりません 13 00:01:32,723 --> 00:01:34,673 3回の挑戦のたびに 14 00:01:34,673 --> 00:01:38,202 塔のくぼみをちょうど満たす エネルギー量を求めるのです 15 00:01:38,202 --> 00:01:42,112 成功すれば エネルギーに乗って 上へと進むことができます 16 00:01:42,112 --> 00:01:46,653 でも量を間違えると エネルギーの昇降機は働かず 17 00:01:46,653 --> 00:01:48,129 下に落ちてしまいます 18 00:01:48,129 --> 00:01:51,348 壁にある図に 例が示されています 19 00:01:51,348 --> 00:01:55,618 この形の場合は 2ユニット分の エネルギーが入ります 20 00:01:55,618 --> 00:02:00,796 この形の場合は 4ユニット分― 左に3つ 右に1つです 21 00:02:00,796 --> 00:02:03,421 この場合も 4ユニット分です 22 00:02:03,421 --> 00:02:06,688 なぜなら 右端に入ったエネルギーは こぼれ出てしまうからです 23 00:02:06,688 --> 00:02:08,812 降り注ぐエネルギーは 24 00:02:08,812 --> 00:02:13,538 周囲に支えるものがなければ あふれてしまうのです 25 00:02:13,538 --> 00:02:19,005 ヘッジはブロックの列を1列ずつ可視化して 高さを測ることができますが 26 00:02:19,005 --> 00:02:22,808 全体の構造を一度に 見ることはできません 27 00:02:22,808 --> 00:02:25,775 エシックがヘッジを どのようにプログラミングすれば 28 00:02:25,775 --> 00:02:29,591 それぞれの塔がくぼみに保持できる エネルギー量を把握できるでしょう? 29 00:02:29,591 --> 00:02:33,120 ビデオをいったん止めて 自分で考えてみましょう 30 00:02:38,805 --> 00:02:41,635 ひとつの考え方は こうです 31 00:02:41,635 --> 00:02:44,638 それぞれの空の箱が エネルギーを保持できるのは 32 00:02:44,638 --> 00:02:48,868 その左方にも 右方にも 壁がある場合です 33 00:02:48,868 --> 00:02:51,602 その左方にも 右方にも 壁がある場合です 34 00:02:51,602 --> 00:02:56,376 でも これを各箱について確認すると 長い時間がかかってしまいます 35 00:02:56,376 --> 00:03:01,185 1列まとめて考えることは できないでしょうか? 36 00:03:01,185 --> 00:03:05,154 例えば この場合は何ユニット分 保持できるでしょう? 37 00:03:05,154 --> 00:03:10,389 [ビデオをいったん止めて 自分で考えてみましょう] 38 00:03:10,389 --> 00:03:13,759 先程の例で 問題を 分析してみましょう 39 00:03:13,759 --> 00:03:15,914 ブロックは5列あります 40 00:03:15,914 --> 00:03:20,484 左端の列は 一番高いので エネルギーを保持できません 41 00:03:20,484 --> 00:03:23,201 2列目は3ユニット分 保持できます 42 00:03:23,201 --> 00:03:27,244 両側にある4段のブロックに 囲まれているからです 43 00:03:27,244 --> 00:03:32,186 エネルギーがいっぱいになる高さ4から 44 00:03:32,186 --> 00:03:36,449 ブロックの高さ1を引いて 3という答えになります 45 00:03:36,449 --> 00:03:41,906 3列目も同様で 左に4段 右に4段あり 高さが3なので 46 00:03:41,906 --> 00:03:46,537 4引く3で1ユニット保持できます 47 00:03:46,537 --> 00:03:51,011 4列目と5列目は 右手に自分より高いものがないので 48 00:03:51,011 --> 00:03:53,473 エネルギーは保持できません 49 00:03:53,473 --> 00:03:57,245 この考え方を アルゴリズムにすることができます 50 00:03:57,245 --> 00:04:01,025 エネルギー量を求めたい列を基準にして 51 00:04:01,025 --> 00:04:05,436 ヘッジは1列ずつ見ていき 左方向で一番高い列を探し 52 00:04:05,436 --> 00:04:08,156 それから右方向でも 一番高い列を探します 53 00:04:08,156 --> 00:04:12,957 その2つの低い方が エネルギーを貯められる高さです 54 00:04:12,957 --> 00:04:16,093 この高さが 列自体の高さよりも高いならば 55 00:04:16,093 --> 00:04:18,671 そこから列の高さを差し引きます 56 00:04:18,671 --> 00:04:23,634 すると その答えが その列に 保持できるエネルギー量になります 57 00:04:23,634 --> 00:04:27,306 エネルギーを貯められる高さが 列自体の高さ以下なら 58 00:04:27,306 --> 00:04:29,614 エネルギーはこぼれてしまいます 59 00:04:29,614 --> 00:04:33,178 ヘッジはループを使って これをすべての列に適用できます 60 00:04:33,178 --> 00:04:38,728 左端の列から右に向かって 1列ずつ調べていくのです 61 00:04:38,728 --> 00:04:41,431 列ごとに同じ手順を踏みます 62 00:04:41,431 --> 00:04:45,547 左方向に一番高い列を探し 右方向に一番高い列を探し 63 00:04:45,547 --> 00:04:49,622 どちらか低い方から 列自体の高さを引いて 64 00:04:49,622 --> 00:04:53,293 その答えが正の数なら 総和にその分を加算します 65 00:04:53,293 --> 00:04:56,988 ヘッジはループを列の数だけ 繰り返します 66 00:04:56,988 --> 00:05:00,954 これで上手くいくのですが サイズが大きいと時間がかかります 67 00:05:00,954 --> 00:05:05,494 ヘッジは各列について左方向と右方向に たどる手順を繰り返すためです 68 00:05:05,494 --> 00:05:10,280 列がN個あると N列すべてをN回参照することになります 69 00:05:10,280 --> 00:05:12,260 もっと速い方法はあるでしょうか? 70 00:05:12,260 --> 00:05:15,608 ひとつの時間短縮法はこうです 手順を進める前に 71 00:05:15,608 --> 00:05:17,468 ヘッジは左端から始めて 72 00:05:17,468 --> 00:05:21,420 各列に対する「左側で一番高い列」を 前もって調べておけます 73 00:05:21,420 --> 00:05:25,215 この場合は まず2 最初の列のほうが高いので 再び2 74 00:05:25,215 --> 00:05:27,921 それから4、4、4、と続きます 75 00:05:27,921 --> 00:05:30,741 それから「右側で一番高い列」も調べ 76 00:05:30,741 --> 00:05:36,960 今度は右から左へ 1、3、4、4、4となります 77 00:05:36,960 --> 00:05:40,722 結果として メモリ上に こんな表が完成します 78 00:05:40,722 --> 00:05:46,143 それから ヘッジはループをもう一回りさせ さっきと同じ計算式を使い 79 00:05:46,143 --> 00:05:50,155 各列に保持できるエネルギーを 計算できます 80 00:05:50,155 --> 00:05:53,662 計算済みの左右の高さの 小さい方から 81 00:05:53,662 --> 00:05:56,789 列自体の高さを引けばいいのです 82 00:05:56,789 --> 00:06:02,293 N列をN回参照する代わりに N列を3回参照するだけでよく 83 00:06:02,293 --> 00:06:04,707 これは線形時間です 84 00:06:04,707 --> 00:06:08,034 この解法をさらに最適化する方法も ありますが 85 00:06:08,034 --> 00:06:10,564 ここでは これで十分でしょう 86 00:06:10,564 --> 00:06:12,614 エシックとヘッジは 力を合わせます 87 00:06:14,992 --> 00:06:19,255 最初の問題は楽勝で 塔を上へと進みます 88 00:06:21,573 --> 00:06:23,988 2つめは ちょっと手強いです 89 00:06:33,051 --> 00:06:37,051 3つめは 大難問で ブロックが何十列もあります 90 00:06:37,051 --> 00:06:41,367 時間が刻々と過ぎますが エシックのプログラムは高速で 91 00:06:41,367 --> 00:06:44,621 ぎりぎりのところで ハンドルの位置を合わせます 92 00:06:49,015 --> 00:06:52,781 エネルギーに乗って 2人は 創造の石のありかへと導かれます 93 00:06:55,640 --> 00:07:01,067 最初のアイテムの時と同じように映像が現れ 何年も前の記憶が蘇ります 94 00:07:01,067 --> 00:07:03,602 世界を動かす機械が すべてを変えてしまい 95 00:07:03,602 --> 00:07:06,794 エシックはロボット主任技術者として 96 00:07:06,794 --> 00:07:09,223 目にする現実に 不安を感じるようになりました 97 00:07:09,223 --> 00:07:12,067 そしてブラッドバリアが人々を 囲い込み始めたとき 98 00:07:12,067 --> 00:07:14,665 何かが決定的におかしいと 気づいたのでした 99 00:07:14,665 --> 00:07:16,984 そこでエシックは 3つのアイテムを作り 100 00:07:16,984 --> 00:07:21,322 「力」「創造性」「記憶」を 人々に取り戻させる力を付与しました 101 00:07:21,322 --> 00:07:24,243 そしてアイテムを3つの共同体に 隠したのです 102 00:07:24,243 --> 00:07:26,541 人々にその使い方を教える前に 103 00:07:26,541 --> 00:07:28,551 政府はエシックのもくろみに気づき 104 00:07:28,551 --> 00:07:32,029 彼女や他のプログラマーを ロボットに逮捕させてしまいました 105 00:07:32,029 --> 00:07:35,295 世界を動かす機械を使って エシックが最後に作ったのは 106 00:07:35,295 --> 00:07:38,355 無知の及ぼす力から この古代の装置を守るため 107 00:07:38,355 --> 00:07:42,381 それを巨大な迷路に 封じ込めるロボットで 108 00:07:42,381 --> 00:07:45,434 そのロボットをヘッジと名付けたのです 109 00:07:51,801 --> 00:07:56,014 警告もなしに エネルギーの昇降機は 突然消えてしまいました