ジュニア問題解説(中学３年生・高校１年生)

• A

  2014-おもしろいまど-解説

  • 正解は次の絵です。

    

    • 問題で，船の両側の窓の絵は、船の先頭が反対方向を向いています。
    • 錨（イカリ）の位置に注目することで，どの窓がどの窓と対応するかを知ることができます。
  • 解説
    • コンピュータは情報を0と1の2種類の値を組合せて扱います。
    • この問題では，左右の窓は0（白）と1（灰色）で表されています。
    • この問題を解くひとつの方法は，ORの演算とXORの演算をすることです。ORは「両方またはどちらかの値が1ならば結果は1（そうでなければ0）」，XORは「どちらか一方の値が1ならば結果は1（そうでなければ0）」という演算です。
      • 窓の色を「0（白）と1（灰色）」と考えてORの演算をすることで結果が「0（白）か1（灰色か黒）」がわかる。
      • 窓の色を「0（白）と1（灰色）」と考えてXORの演算をすることで結果が「0（白か黒）か1（灰色）」がわかる。
    • もうひとつの方法は，それぞれの窓を「0（白）と1（灰色）」という数字で並べて足し算をすることです。すると「0 1 1 1 0 0 1 0」＋「0 0 0 1 1 0 1 1」＝「0 1 1 2 1 0 2 1」という結果になり，「0の窓は白，1の窓は灰色，2の窓は黒」に見えることがわかります。
  • 出題国: この問題はカナダで作成されました。

  2014-中国のそろばん-解説

  • 正解は「7014831」です。
  • 試してみよう
    • 珠（たま）を動かすと，どのような数を表すことができるか試してみましょう。
  • 解説
    • 人類は古くから，置いた石や珠を動かすことで，足し算や掛け算などの計算を行ってきました。それを道具にしたものがそろばんです。この問題では中国で使われている算盤と呼ばれるそろばんの仲間が使われています。
    • 私たちがそろばんで計算をするときは，「計算したい数を珠で表す」「計算を行う」「計算した結果を読み取って数に直す」という作業を行います。
    • これはコンピュータでデータを扱うときの「扱いたいものをコンピュータで扱える文字や数値で表す（符号化）」「コンピュータで処理する」「結果を人間にわかりやすいように出力する（復号）」という処理に対応しています。
    • たとえば，携帯電話で友だちにメールするときは，「入力した文字は携帯電話に内蔵されたコンピュータによって文字コードという数値に変換され」「携帯電話から相手の携帯電話に転送され」「相手の携帯電話のコンピュータによって数値から文字に変換されて表示される」という処理が行われています。
    • そろばんは人類が作った最初のコンピュータかもしれません。
  • 出題国: この問題はスイスで作成されました。

  2014-回転寿司-解説

  • 正解は「サーモン， ホタテ， エビ」です。
    • 3人は流れてくる4種類の寿司を順番に取っていきます。
    • 流れてくる寿司から順番に3個ずつ取ったときはこのようになっています。

      ビ太郎	ビバ子	マイ子	ビ太郎	ビバ子	マイ子	ビ太郎	ビバ子	マイ子
      エビ	ホタテ	サーモン	巻き寿司	エビ	ホタテ	サーモン	巻き寿司	エビ

  • 解説
    • この問題では，規則に基づくコンピュータの資源割り当てを扱っています。
    • 例えば，コンピュータの記憶装置では，一続きのデータを分割し複数のディスクに書いていくことにより，データを記録する速度を高める工夫がなされていることがあります。
    • この問題では，お客はファイルでお皿は記憶装置と見立てることができます。
  • 出題国: この問題は日本で作成されました。

  2014-貨物船-解説

  • 正解
    • １つの船に「120 90 90」の組合せで樽をのせ，もう1つの船に「130 100 60」の組合せで樽をのせると，2隻の船に積む樽の重さの合計が最大になります。
    • 非対話型問題では「「100 130 60」と「120 90 90」」が正解です。
      • 非対話型の選択肢を検討すると次のようのになります。

        Lisa1の船		Lisa2の船		合計
        220 60	280kg	130 120 90	340kg	重量オーバー
        130 90 60	280kg	120 100 90	310kg	重量オーバー
        120 90 90	300kg	220 60	280kg	合計580kg
        100 130 60	290kg	120 90 90	300kg	合計590kg（正解）

  • 解説
    • さまざまな組み合わせの中から「制限の中で最大の荷物を載せる」という最適な組み合わせを見つけ出す問題です。
    • 数がそれほど多くないもの同士の組み合わせでも，組合せ方は膨大になることがあります。そのため，コンピュータは高速に計算などを行えますが，すべての場合を調べてると時間がかかってしまいいつまでも処理が終わらないことがあります。
    • 現在も効率良く最適解を求めるアルゴリズムの研究が続けられています。
  • 出題国: この問題はドイツで作成されました。
• B

  2014-みつばちロボット-解説

  • 正解は「四角， 進む， 回る， 三角」です。
    • 「四角， 回る， 進む， 三角」では，みつばちロボットはこのように描きます。
      
    • 「四角， 進む， 回る， 三角」では，みつばちロボットはこのように描きます。
      
    • 「三角， 回る， 四角」では，みつばちロボットはこのように描きます。
      
    • 「四角， 進む， 四角， 回る， 三角」では，みつばちロボットはこのように描きます。
      
  • 試してみよう
    • 命令をどのように組み合わせると，みつばちロボットがどのように動くか試せます。
  • 解説
    • コンピュータは命令を順番に実行することでさまざまな処理を行います。この問題は命令を順番に実行するコンピュータの処理を表しています。
    • この問題で使われた「前進や回転の命令で移動し，移動した軌跡が線として残る」仕組みは，LOGOという教育用のプログラミング言語で提案され，現在もドリトルやScratchなどの言語で使われています。
  • 出題国: この問題はスロバキアで作成されました。

  2014-ダム-解説

  • 正解は11時間です。
    • 下の絵のように，水は川から1時間に1マスずつ草地に入ってきます。
    • 最後の草地に水が入るのは11時間後です。

      

  • 試してみよう
  • 解説
    • この問題では，水が草地に入っていくときに複数の経路（道）を通ります。そして、それぞれの経路の水は出発点から同じ速さで進んでいきます。
    • このような複数の経路を同じ速さで並行して調べていく探索を「幅優先探索」と呼んでいます。（ひとつの経路をいちばん奥まで調べてから他の経路を探す探索は「深さ優先探索」と呼ばれます。）
  • 出題国: この問題はリトアニアで作成されました。

  2014-川上り-解説

  • 正解は「スタート → B → C → D → E → ゴール」です。
    • 「スタート → A → C → E → ゴール」は2+5+5+5=17の体力を消費します。
    • 「スタート → A → C → E → D → ゴール」は2+5+5+2+3+5=22の体力を消費します。
    • 「スタート → B → C → D → E → ゴール」は3+3+2+2+5=15の体力を消費します。（最も小さいので正解です）
    • 「スタート → B → C → D → ゴール」は3+3+2+3+5=16の体力を消費します。
  • 試してみよう
    • どの順番で移動すると，どのように体力を消費するか試してみよう。
  • 解説
    • スタートとゴールと A から E の7箇所の地点と，それらの間を移動できる９本の川の区間は，点と線によるグラフ構造で表すことができます。川の区間上にある通過すると体力を消費する障害物は，その区間の距離とみなせます。この問題では，スタートからゴールまでの最短経路を求めます。（実際には，距離が15以下の経路を見つけます。）
    • 線に距離が決められたグラフ上で2点間を結ぶ最短経路を求めるアルゴリズムは，最短時間の移動経路や最も安く移動できる経路の探索などに利用されています。
  • 出題国: この問題は日本で作成されました。

  2014-村のスピーカー-解説

  • 正解は「3」です。
    • 2個のスピーカーではすべての家にお知らせを届けることはできません。
    • 3個のスピーカーでは，次のどちらかの置き方で，すべての家にお知らせを届けることができます。

      　

  • 試してみよう
    • 線と線が交わる場所をクリックすると，そこにスピーカー（★印）を置けます。
    • スピーカー（★印）をクリッすると，そのスピーカーを取り除けます。
  • 解説
    • できるだけ少ない機器で必要なエリア（領域）をカバーする技術は，携帯電話の通信用のアンテナをどのように配置するかといった形で世の中で使われています。
  • 出題国: この問題は日本で作成されました。
• C

  2014-丸太の作品-解説

  • 正解は次の形です。

    

    • 1回目の置き換え後に正解の形になる規則を用いると，2回目の置き換え後に問題の形になっていることがわかります。

      

  • 解説
    • コンピュータは少数のルールを繰り返し適用することで複雑な動作を行っています。
    • この問題では，1本の線を複数の線で置き換えていきますが，これは「再帰的アルゴリズム」と呼ばれる考え方です。
    • この問題中の規則に従い描かれる絵は，自己相似が無限に繰り返される「フラクタル」と呼ばれている図形となります。
  • 出題国: この問題はスイスで作成されました。

  2014-儀式-解説

  • 正解
    • 図をわかりやすく描き直すと，次のようになります。
      
    • 対話形式の問題では，作成した行事予定がこの図に当てはまる順序になっていれば正解です。
      • たとえば「Choir Singing(聖歌隊合唱), Boring Speeches(退屈な挨拶) , Lottery(抽選会), Drum Roffle(太鼓連打), Musical Intemezzo(間奏曲演奏), Fanfare(ファンファーレ), Fireworks(花火), Thank you(謝辞)」は正解の1つです。
    • 他にも以下が正解です。（最初の「Choir Singing」と最後の「Thank you」は省略しています。）
      • 「Drum Roffle」 - 「Boring Speeches」 - 「Lottery」 - 「Musical Intermezzo」 - 「Fanfare」 - 「Fireworks」
      • 「Drum Roffle」 - 「Boring Speeches」 - 「Musical Intermezzo」 - 「Fanfare」 - 「Fireworks」 - 「Lottery」
      • 「Drum Roffle」 - 「Boring Speeches」 - 「Musical Intermezzo」 - 「Fanfare」 - 「Lottery」 - 「Fireworks」
      • 「Drum Roffle」 - 「Boring Speeches」 - 「Musical Intermezzo」 - 「Lottery」 - 「Fanfare」 - 「Fireworks」
      • 「Boring Speeches」 - 「Drum Roffle」 - 「Lottery」 - 「Musical Intermezzo」 - 「Fanfare」 - 「Fireworks」
      • 「Boring Speeches」 - 「Drum Roffle」 - 「Musical Intermezzo」 - 「Fanfare」 - 「Fireworks」 - 「Lottery」
      • 「Boring Speeches」 - 「Drum Roffle」 - 「Musical Intermezzo」 - 「Fanfare」 - 「Lottery」 - 「Fireworks」
      • 「Boring Speeches」 - 「Drum Roffle」 - 「Musical Intermezzo」 - 「Lottery」 - 「Fanfare」 - 「Fireworks」
    • 非対話形式の問題では，図の規則に合っていない選択肢は "Drum, Musical, Fanfare, Boring, Lottery, Fireworks" です。"Boring" が "Musical" の後に置かれてしまっています。
  • 解説
    • この問題では，対象を「ノード（頂点）」と「エッジ（辺）」で表すグラフ表現を扱っています。
    • この問題で，儀式の行事は順序を示す矢印で結ばれた有向グラフとして表現されています。
    • コンピュータでは，グラフ構造を利用することで複雑なデータを表現したり、鉄道の経路探索のような複雑な問題を扱ったりしています。
    • この問題の図を上の図のように並び替えることはトポロジカルソートと呼ばれるもので，エッジを出している（矢印の元）ノードが，そのエッジが入る（矢印の先）ノードよりも前に置くように並び替えます。これにより，この問題のように前に行われていなければいけない行事があるときのスケジューリングを考えることができます。
  • 出題国: この問題はフランスで作成されました。

  2014-動きの検出-解説

  • 正解は「画像11をその１秒前の画像と比較した時」です。
    • この問題のコンピュータは「左から右への動き」を検出したときにベルを鳴らします。
    • それぞれの画像は次のような状態になります。

      画像0	状態A
      画像1	状態A
      画像2	状態A
      画像3	状態A
      画像4	状態B
      画像5	状態A
      画像6	状態B
      画像7	状態B
      画像8	状態C
      画像9	状態C
      画像10	状態C
      画像11	状態A（ベル）

  • 解説
    • 空港のようなセキュリティが重要な区域には監視カメラが設置されて画像を記録しています。
    • 監視カメラはコンピュータにも接続されていて，区域に入った人数を数えたり、危ない行動を検知したりします。
    • 行動を検知するプログラムはこの問題と同様に動きの状態を利用しています。
  • 出題国: この問題はドイツで作成されました。

  2014-翻訳マシン-解説

  • 正解は次の図です。

    

    • 通り道の得点が左から順に「6→5→6→5」となり，点数は「22」になります。
    • 効率よく解を求めるには，左の英単語から順に，それらの下の記号までの点数の最大を求めていくと良いでしょう。
  • 解説
    • 正解に書かれている解法は，「動的計画法」と呼ばれている方法です。
  • 出題国: この問題はチェコで作成されました。

  2014-背くらべ-解説

  • 正解は「Diggy, Amy, Cuttree, Beavy, Eary」です。
    • 問題は2段階で考えていきます。
    • 最初はそれぞれのビーバーについて，自分より背の高いビーバーが何人いるかを数えます。そして背の低い順に1,2,3,4,5の番号を付けます。
      • まず，Diggyより大きいビーバーはいないので5にします。
      • 次に，Cuttreeより大きいビーバーは1人しかいないので4にします。
      • 同様に，Earyを3，Amy２を2，Beavyを1にします。
    • 次にそれぞれのビーバーについて、自分より背の高いビーバーが前と後に何人いるかを考えます。
      • Cuttreeは前に自分より大きなビーバーが1人いますので，Diggyより後にいることがわかります。
        「（前）　　D5　　C4　　（後）」
      • Earyは前に自分より大きなビーバーが2人いますので，DiggyとCuttreeより後にいることがわかります。
        「（前）　　D5　　C4　　E3　　（後）」
      • Amyは前に自分より大きなビーバーが1人，後に自分より大きなビーバーが2人いますので、DiggyとCuttreeの間にいることがわかります。
        「（前）　　D5　　A2　　C4　　E3　　（後）」
      • Beavyは前に自分より大きなビーバーが3人，後に自分より大きなビーバーが1人いますので、CuttreeとEryの間にいることがわかります。
        「（前）　　D5　　A2　　C4　　B1　　E3　　（後）」
  • 解説
    • この問題ではデータの並び替えを扱っています。
    • さまざまな問題を扱うときに、最初にデータを並び替えてみるのはよい方法です。
  • 出題国: この問題はスウェーデンで作成されました。

（ジュニア問題に戻る）