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

• A

  2013-ビーバートンネル-解説

  • 正解は
    
    
    
    • 最初の黒いトンネルを通ると
      
      
    • 次の白いトンネルを通ると
      
      
    • 最後の黒いトンネルを通ると
      
      このような順番になります。

  2013-回転とびら-解説

  • 正解は「Ｂ」
    • 赤・青・黄のボールが，それぞれの回転とびらで，どちら側のパイプに落ちるかを順に考えていきます。
      • 最初(上)にある回転とびらでは，赤は左，次の青は右，次の黄色は左に落ちます。左側には赤と黄色，右側には青のボールが落ちます。
      • 黄色のボールは，左側のパイプに落ちますので，左側(Ａ,Ｂ側)の回転とびらで考えます。
      • ２つ目(下)にある左側(Ａ,Ｂ側)の回転とびらでは，赤はＡ，次の黄色はＢへ落ちます。

  2013-ビーバー音楽-解説

  • 正解は「CDBD」
    • 「回数[ … ]」で繰り返しているところを，繰り返しを使わない形にもどすとよい。
    • ポン 2[ポ]/4[ポ]/ポン 2[ポ]/ポーン/2[4[ポ]/]ポン2[ポ]/ポーン
      ↓
      ポンポポ/ポポポポ/ポンポポ/ポーン/ポポポポ/ポポポポ/ポンポポ/ポーン
      ↓
      「ポンポポ/ポポポポ/」「ポンポポ/ポーン/」「ポポポポ/ポポポポ/」「ポンポポ/ポーン」
      ↓
      「C」「D」「B」「D」
  • 解説
    • コンピューターのプログラムでは，命令を繰り返して実行できます。
    • この問題では，音を出す命令を何回繰り返して実行するかを，数字と括弧で表現しています。
      • 例: 数[命令]は，命令を数の回数だけ繰り返します。
      • 例: 数2[数1[命令]]は，「命令を数1の回数だけ繰り返す動作」を数2の回数だけ繰り返します。結果として命令が「数1×数2」回実行されます。

  2013-お手伝い-解説

  • 正解は 3 回水を移す です。

    

    • 2回では 5L と 3L に分けられません。
    • 1回水を移すと，「4L と 4L」か「7L と 1L」に分けられます。
      • 「4L と 4L」からもう1回水を写すと，「4L と 3L と 1L」に分けられます。
      • 「7L と 1L」からもう1回水を写すと，「4L と 3L と 1L」に分けられます。
  • 解説
    • この問題は木探索に関連しています。
    • 初期状態から始めて，遷移可能な状態を順次探索していきます。
• B

  2013-救助活動-解説

  • 正解は 出口B です。

    

  • 解説
    • 閉路を持たない連結なグラフのことを木といいます。木の探索／走査（トラバース）は，情報科学のさまざまな問題を解決するのに重要な役割を果たします。

  2013-折り曲げ機械-解説

  • 正解は 9回 です。
    • 1回折り曲げると2個の三角形ができます。
    • 2回折り曲げると4個の三角形ができます。
    • 3回折り曲げると8個の三角形ができます。
    • 4回折り曲げると16個の三角形ができます。
    • 5回折り曲げると32個の三角形ができます。
    • 6回折り曲げると64個の三角形ができます
    • 7回折り曲げると128個の三角形ができます
    • 8回折り曲げると256個の三角形ができます。
    • 9回折り曲げると512個の三角形ができます。
    • 10回折り曲げると1024個の三角形ができます。
    • 11回折り曲げると2048個の三角形ができます。
  • 解説
    • 2のべき乗に関する問題です。

  2013-空港-解説

  • 正解は
    　
    
    
    • 順番に荷物をのせていくと次のようになります。
      • 1．
        
      • 2．
        
      • 3．
        
        
        
      • 4．荷物がのっている場所は数えません。なので、次の場所に黄色の荷物をのせます。
        
        
        
      • 5．荷物がのっていない場所を２つ見送ると、すでにむらさき色の荷物があるので、次に回ってくる荷物のない場所にのせます。
        

  2013-のろし-解説

  • 正解は 5分 です。
    • 図では，狼煙（のろし）が見える場所同士を線で結んでいます。
    • 将軍の住んでいるお城と線で結ばれている場所では，1分後に狼煙があがります。そこで，将軍の住んでいるお城と線で結ばれている場所に 1 と書き込みます。
    • 最初に将軍の住んでいるお城で狼煙があがってから2分後には，1 が書き込まれた場所と線で結ばている場所で狼煙があがります。そこで，それらの場所に（1が書かれていなければ）2と書き込みます。
    • これをすべての場所に時間が書き込まれるまで繰り返すと次の図のようになります。

      

    • あとは，この図の中から一番大きな値（時間）を探すだけです。
  • 解説
    • このような問題を解決する際，グラフは有用です。
    • グラフは，ある集合の要素を対象（この場合は，狼煙をあげる場所の集合）とし，ある規則でつなぐ／対にする（この場合は，狼煙が見える場所同士ならつなぐ／対にする）ものです。対象を「頂点」と呼び，つながりを「辺」と呼びます。
    • 通信網やウェブページのリンク構造などのネットワークを表すのに，グラフは良く用いられます。
    • 最短経路を求めるアルゴリズムは，グラフで考えられる問題に対するアルゴリズムの代表例です。
    • この解法では，幅優先探索と呼ばれるアルゴリズムを用いました。
• C

  2013-回すオモチャ-解説

  • 正解は「ひだり→みぎ→みぎ→ひだり→みぎ→ひだり」
    • ビー玉を出すためには，下の図のような経路をたどる必要があります。
      
      そのためには，下の図のような順番で木の板を回せばよいのです。
      

  2013-迷宮-解説

  • 正解は「1 1 3 2 3 3 4 4 1 4 2 2」
    • 壁にぶつからずに，元の場所に戻ってこられるプログラムを探します。
      • 「1 1 3 2 3 3 4 4 1 4 2 2」は，「←←↑→↑↑↓↓←↓→→」となり，壁にぶつからずに元の場所まで戻れます。
      • 「1 1 3 2 3 1 2 4 1 4 2 2」は，「←←↑→↑←→↓←↓→→」となり，６つ目の命令(←)で壁にぶつかります。
      • 「1 1 3 2 3 3 4 3 1 4 2 2」は，「←←↑→↑↑↓↑←↓→→」となり，８つ目の命令(←)で壁にぶつかります。
      • 「1 1 3 2 3 3 4 4 1 4 2」は，「←←↑→↑↑↓↓←↓→」となり，１つ手前で止まり元の場所まで戻れません。

  2013-サイコロ-解説

  • 正解は「描画2, 回転90, 描画2, 描画3」
    • 描画2が取り得る形は
    • 描画3が取り得る形は
    • を作るには、描画2を90度回したものと、描画2と描画3をそのまま配置したもので実現可能
    • 描画2 -> 回転90 -> 描画2, 描画3

  2013-ネックレス-解説

  • 正解は「32」
    • 最も短い長さを探します。
      
    • 考えられる最短の紐は、(A,B,E,H,I)か (A,C,D,F,G,I)
      • AD > ACDおよび GHI > GIのため、除外
    • (A,B,E,H,I)は 6+8+8+6+4+3 = 35
    • (A,C,D,F,G,I)は 6+8+2+6+4+3+3 = 32 <=最短

（カデット問題に戻る）