Placeholder Image

字幕表 動画を再生する

  • Ethic, Hedge, and Octavia stand on the edge of a bottomless ravine.

    エシック、ヘッジ、オクタヴィアは 底なしの谷の縁に立っています

  • It's the only thing between them and the tower

    塔と彼らを隔てる この谷さえ渡れば

  • that houses the second of three powerful artifacts.

    3つの強力なアイテムの 2つめが手に入るのです

  • They've got a brief window of time to get across before the guards return.

    警備ロボットが戻ってくるまでの 短い時間に渡らなければなりません

  • With Hedge's fuel gauge on empty he won't be able to fly Ethic across,

    ヘッジが燃料切れで エシックを連れて飛べないので

  • so the only option is to make a bridge.

    橋を作るしかありません

  • Fortunately, the floating stacks of stones nearby are bridge components

    幸い 橋の部品となるブロックの山が 近くに浮かんでいます

  • invented by Octavia herselfcalled hover-blocks.

    オクタヴィアが発明した 浮遊ブロックです

  • Activate a pile with a burst of energy,

    エネルギーをかけて ブロックの山を起動させれば

  • and they'll self-assemble to span the ravine as Ethic walks across.

    エシックが歩いて渡れる橋が 自動的に組み上がります

  • But there is, of course, a catch.

    もちろん 問題もあります

  • The hover-blocks are only stable when they're perfectly palindromic.

    浮遊ブロックが安定するのは 完全な回文構造の時だけなのです

  • Meaning they have to form a sequence

    つまり 前から見ても 後ろから見ても

  • that's the same when viewed forwards and backwards.

    並び順が同じでなければなりません

  • The stacks start in random orders,

    ブロックは最初ランダムに 積み重なっていても

  • but will always put themselves into a palindromic configuration

    可能な限り 回文構造を作ろうとします

  • if they can.

    可能な限り 回文構造を作ろうとします

  • If they get to a point where a palindrome isn't possible,

    回文構造が作れないときには

  • the bridge will collapse,

    橋は崩れてしまい

  • and whoever's on it will fall into the ravine.

    上にいる人は 谷底に落ちることになります

  • Let's look at an example.

    例を見てみましょう

  • This stack would make itself stable.

    このブロックの山は 安定した構造を作れます

  • First the A blocks hold themselves in place.

    まずAが両端につきます

  • Then the B's.

    それからBがきて

  • And finally the C would nestle right between the B's.

    最後にCが Bの間に入ります

  • However, suppose there was one more A.

    でもAが もう1つあったとしたら?

  • First two A blocks form up, then two B's,

    まずはAが2個 次にBが2個 入りますが

  • but now the remaining C and A have nowhere to go,

    残ったCとAには 行き場がないので

  • so the whole thing falls apart.

    全体が崩れてしまいます

  • The Node of Power enables Hedge to energize a single stack of blocks.

    力の石を使ってヘッジは ブロックの山を1つだけ起動できます

  • What instructions can Ethic give Hedge to allow him to efficiently find

    エシックがどんな指示を ヘッジに与えれば

  • and power a stable palindromic stack?

    回文構造を作れる山を効率的に見つけ 起動させられるでしょうか?

  • Pause now to figure it out for yourself.

    [ビデオをいったん止めて 自分で考えてみましょう]

  • Examples of palindromes include ANNA, RACECAR, and MADAM IM ADAM.

    回文の例としては ANNAや RACECARや MADAM IM ADAMなどがあります

  • Counting the number of times a given letter appears in a palindrome

    回文の中に各文字が 何度現れるかを数えると

  • will reveal a helpful pattern.

    役に立つ規則性が 見えてくるでしょう

  • Pause now to figure it out for yourself.

    [ビデオをいったん止めて 自分で考えてみましょう]

  • Let's first look at a naïve solution to this problem.

    まずは 素朴な解決法を 考えてみましょう

  • A naïve solution is a simple, brute-force approach that isn't optimized

    素朴な方法とは 最適化されていない 単純なしらみつぶしのやり方ですが

  • but will get the job done.

    目的は果たせるような もののことです

  • Naïve solutions are helpful ways to analyze problems,

    素朴な方法は 問題を分析する役に立ち

  • and work as stepping stones to better solutions.

    よりよい解決法を見つける 糸口になります

  • In this case, a naïve solution is to approach a pile of blocks,

    この場合 素朴な方法は ブロックの山ごとに

  • try all the arrangements,

    すべての並び順を試し

  • and see if one is a palindrome by reading it forward and then backwards.

    前からも 後ろからも読んで 回文構造か確かめるというものです

  • The problem with this approach

    この方法の問題は

  • is that it would take a tremendous amount of time.

    とても長い時間がかかることです

  • If Hedge tried one combination every second,

    ヘッジが1つの並びを試すのに 1秒かかるとすると

  • a stack of just 10 different blocks would take him 42 days to exhaust.

    異なる10個のブロックからなる山を 1つ調べるのに42日間もかかります

  • That's because the total time is a function of the factorial

    なぜなら かかる時間は ブロックの個数の

  • of the number of blocks there are.

    階乗に等しくなるからです

  • 10 blocks have over 3 million combinations.

    ブロックが10個なら 3百万以上の並び順があります

  • What this naïve solution shows is that we need a much faster way

    この素朴な方法から分かるのは もっと速い方法で

  • to tell whether a pile of blocks can form a palindrome.

    ブロックの山が回文構造になるか 見分ける必要があるということです

  • To start, it may be intuitively clear that a pile of all different blocks

    まず 直観的に分かるのは

  • will never form one.

    「ブロックが全部違っていたら不可」 ということです

  • Why?

    なぜなら 重複しているブロックがなければ 両端のブロックが同じになり得ないからです

  • The first and last blocks can't be the same if there are no repeats.

    では 回文構造になり得るのは どのような場合なのでしょう?

  • So when can a given sequence become a palindrome?

    いくつかの回文を分析することで 答えを見つけることができます

  • One way to figure that out is to analyze a few existing palindromes.

    ANNA には Aが2個 Nが2個あります

  • In ANNA, there are 2 A's and 2 N's.

    RACECAR には Rが2個 Aが2個、Cが2個、Eが1個

  • RACECAR has 2 R's, 2 A's, 2 C's, and 1 E.

    MADAM IM ADAM には Mが4個 Aが4個、Dが2個、Iが1個です

  • And MADAM IM ADAM has 4 M's, 4 A's, 2 D's, and 1 I.

    ここで見られるパターンは

  • The pattern here is that most of the letters occur

    ほとんどの文字が偶数回 現れているということです

  • an even number of times,

    そして1回しか現れない文字は あっても1つだけです

  • and there's at most 1 that occurs just once.

    それだけでしょうか?

  • Is that it?

    RACECAR にEが1個でなく 3個あったとしたら?

  • What if RACECAR had 3 E's instead of 1?

    増えたEを両端につければ また回文構造になるので

  • We could tack the new E's onto the ends and still get a palindrome,

    3回現れてもOKです

  • so 3 is ok.

    でも Eが3個で Cも3個なら 最後のCの行き場がなくなります

  • But make that 3 E's and 3 C's, and there's nowhere for the last C to go.

    ですから 一般化した考え方は

  • So the most generalized insight is that

    奇数回現れる文字は 多くて1個で

  • at most one letter can appear an odd number of times,

    残りの文字はすべて偶数回現れる ということです

  • but the rest have to be even.

    ヘッジはブロックの山ごとに 文字の出現回数を数えて辞書の形に整理でき

  • Hedge can count the letters in each stack and organize them into a dictionary,

    これは上手い情報格納法です

  • which is a tidy way of storing information.

    ここでループを使って 奇数が何度現れるかを数えます

  • A loop could then go through and count how many times odd numbers appear.

    奇数回現れる文字が2個未満であれば そのブロックの山は回文構造にできます

  • If there are less than 2 odd characters, the stack can be made into a palindrome.

    このやり方は 素朴な方法よりも ずっと速く実行でき

  • This approach is much, much faster than the naïve solution.

    文字数の階乗時間ではなく 線形時間しか かかりません

  • Instead of factorial time, it takes linear time.

    つまり ブロックの数に 比例した時間しか

  • That's where the time increases

    かからないということです

  • in proportion to the number of blocks there are.

    ヘッジがそれぞれの山を分析して

  • Now write a loop for Hedge to approach the piles individually,

    回文になるものを見つけ次第 やめるようなループを書いたら

  • and stop when he finds a good one, and you'll be ready to go.

    準備は万端です

  • Here's what happens:

    さて どうなるでしょう

  • Hedge is fast, but there are so many piles it takes a long time.

    ヘッジは素早いものの 山がたくさんあって手間取り

  • Too long.

    時間がかかりすぎました

  • Ethic and Hedge are safe.

    エシックとヘッジは無事でしたが

  • But Octavia is not so lucky.

    オクタヴィアは 運が悪かったようです

Ethic, Hedge, and Octavia stand on the edge of a bottomless ravine.

エシック、ヘッジ、オクタヴィアは 底なしの谷の縁に立っています

字幕と単語

動画の操作 ここで「動画」の調整と「字幕」の表示を設定することができます

B1 中級 日本語 TED-Ed ブロック ヘッジ 文字 奇数 起動

ザ・チャズム|Think Like A Coder, Ep 6 (The Chasm | Think Like A Coder, Ep 6)

  • 26 0
    ally.chang に公開 2021 年 01 月 14 日
動画の中の単語