カデット問題解説(中学１年生・２年生)

• A

  2014-ビ太郎を探せ-解説

  • 正解は「8」です。

    

    • ビーチパラソルのある写真は「2,5,7,8」です。
    • 帽子をかぶっていない写真は「3,4,7,8」です。候補（こうほ）は「7,8」に絞られました。
    • 海が写っている写真は「1,2,4,8」です。候補（こうほ）は「8」だけになりました。
  • 解説
    • この問題は，ビットを用いた情報の表現を扱っています。
    • コンピュータはすべての情報を「はい」と「いいえ」，「真」と「偽」，「オン」と「オフ」，「0」と「1」のような2種類の値を組み合わせて扱っています。ビットは情報を表す基本単位で，1ビットで「0か1か」などの2種類の状態を表すことができます。
    • 1ビットで「0, 1」という2種類の情報しか表せませんが，2ビットで「00, 01, 10, 11」という4種類を表せます。3ビットで「000, 001, 010, 011, 100, 101, 110, 111」という8種類を表せるようになります。このように，コンピュータは2種類の値だけを扱いますが，この2種類の値を組み合わせることで，複雑なことを表現できます。
    • この問題では，3つのビ太郎の質問に対するビバ子の返事の3ビットで，8種類の絵すべてを表現できます。つまり，ビバ子が8種類の絵からどれを選んだとしても，ビ太郎は「はい/いいえ」で答えられる質問を3回することで必ず正解を選ぶことができます。
  • 出題国: この問題は日本で作成されました。

  2014-ブレスレット-解説

  • 正解は下の絵です。

    

    • 正解のブレスレットは「13個の真珠（しんじゅ）」があり，「5個の黒い真珠（しんじゅ）」があり，「黒い真珠（しんじゅ）が2個続いている部分が1ヶ所」あるものです。

      

    • 正解以外のブレスレットは，真珠（しんじゅ）の数が12個だったり，黒い真珠（しんじゅ）が6個あったり，黒い真珠（しんじゅ）が2個続いている部分がなかったりしています。
  • 解説
    • この問題では，真珠を使って並びのパターンを表しています。
    • コンピュータでは，特定の文字の並びを検索することでWeb検索や文書検索を行ったり，特定の画素（ピクセル）の並びを検索することで画像検索を行ったりしています。
    • データの並びによる検索は，日本語入力のときに入力された読みから漢字の候補を検索するときにも使われており，携帯電話やスマートフォンでも使われる重要な技術になっています。
  • 出題国: この問題はチェコで作成されました。

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

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

  2014-回転寿司-解説

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

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

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

  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-ダム-解説

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

      

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

  2014-木をたおそう-解説

  • 正解は「15分」です。
    • 「2匹が同時に2本の木をかじって倒（たお）してから，残りの1本を1匹がかじって倒す」と，10分と10分で合計20分が必要です。
    • しかし，作業を工夫することで15分で3本の木を倒（たお）すことが可能です。
      • ビーバーAは木1を5分間だけかじり，続いて木2を10分間かじって倒（たお）します。
      • ビーバーBは木3を10分間かじって倒（たお）した後、続いて木1を5分間かじって倒（たお）します。

        

  • 解説
    • これは作業のスケジュールを考える問題です。
    • コンピュータの内部では，1個から数個のCPUが数多くの処理を短い時間で切り替えながら実行しています。また，大量のデータの通信やプリンタでの印刷など時間のかかる処理も行っています。
    • この問題のように，作業の割り当て方によって全体の処理時間が変わってしまうため，どのような処理にどれくらいの時間を割り当ててどのような順序で処理を行うかということは重要な問題です。
  • 出題国: この問題はオーストラリアで作成されました。

  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（正解）

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

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

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

  2014-モンスター-解説

  • 正解は「6」です。
    • 黄色の部屋は127個あります。
    • 真ん中の64番目の部屋をクリックすると，モンスターのいる部屋を63個に絞れます。
    • 続けて，63個の真ん中の部屋をクリックして31個に絞り，もう一度クリックして15個に絞る，という作業を続けていくと，6回のクリックでモンスターを1個の部屋に閉じ込められます。
      127→63→31→15→7→3→1
  • 解説
    • この問題では大量のデータの中から目的のデータを探す「二分探索」を扱っています。
    • 二分探索を使うと，並びの真ん中を見て目的のデータがどちら側にあるかを調べることで、目的のデータを効率よく探すことが可能です。
    • この例では，端から1個ずつクリックして調べていくと全部の部屋を調べるのに127回かかってしまいますが，半分ずつ調べていくことにより6回で探すことができました。
  • 出題国: この問題はフランスで作成されました。

  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個のスピーカーでは，次のどちらかの置き方で，すべての家にお知らせを届けることができます。

      　

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

（カデット問題に戻る）