CadetAnswer2023

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

• A

  2023-ある日の動物園-解説

  • 考案国：オーストリア
  • 正解
    • 5
  • 説明
    • この問題を解決する方法の一つは，重ならないショーの可能な組み合わせをすべて試すことです。重ならないショーの組み合わせは，実際に見ることが可能なスケジュールです。その後，見ることができるショーが最も多いスケジュール（最適なスケジュール）を確認します。この方法は，全探索やしらみつぶし探索などと呼ばれます。
    • 解決すべき問題によっては，全探索では確認しないとならない組み合わせが多くなり，現実的な時間で解が得られないことがあります。
    • 問題をよく観察することで，問題を簡単にする緒（いとぐち）を見出すことができます。もし２つのショーの時間が重なっている場合，最適なスケジュールに含まれるのはどちらか1つのショーだけです。これら２つのショーのうち，1つのショーの時間がもう１つのショーの時間に完全に他に含まれている場合は，短い時間のショーを選ぶべきです。
      
    • 例えば，鳥のショー の時間は魚のショー の時間に含まれています。
      魚のショー を選ぶのなら， 鳥のショー を選んだ方が，これら２つ以外のショーと重なる可能性が小さくなります。
      よって，鳥のショー は考察から外すことができます。
    • 同じ理由で，次のことが言えます。
      • ヘビのショー はカンガルーのショー の間に行われるので， カンガルーのショー を考察から外すことができます。
      • クマのショー は象のショー の間に行われるので， 象のショー を考察から外すことができます。
        
    • これら３つのショーを取り除くと，残ったショーは次の図のようになります:
      
    • これらのショーを時間が重ならならない３つのグループに分けて， A, B, C を名前をつけることにします。すると，それぞれのグループで最適なスケジュールを求めることで，1日全体の最適なスケジュールを求めることができます。
      
      • グループ A には，鳥のショー だけが含まれています。そこで最適なスケジュールに鳥のショー を入れます。
      • グループ B には3つのショーが含まれています。
        グループ B を全探索すると実現可能なスケジュールは２つです。
        
        グループ B から最適なスケジュールに入れるのはクモのショー とヘビのショー です。
      • グループ C にも3つのショーが含まれています。同じように全探索することで，グループ C からはアザラシのショーtとコアラのショーを最適なスケジュールに入ることが分かります。
    • これらをまとめると1日全体の最適なスケジュールは次の図のようになります:
      このスケジュールには5つのショーが含まれているので，正解は 5 です。
  • 実際のコンピュータでは
    • 情報学において，問題を解決するアルゴリズムを設計する際，最も簡単に思いつくアルゴリズムは，全探索・しらみつぶし探索です。この探索法は，概念が単純でかつ正しい答えを保証します。しかし，全探索は手作業やコンピュータで行うにも時間がかかりすぎることです。もっと高速に問題を解決するためのより効率的なアルゴリズムを見つける必要があります。
    • アルゴリズムをより効率化するには，問題を良く観察して，問題を解決するのに必要な項目だけを抜き出すことが重要となります。このことを，簡略化や抽象化と呼ぶことにします。解の値を最大化または最小化する問題は最適化問題と呼ばれます。最適化問題を簡略化する際に，最適な解を得るための情報は残す必要があります。この問題では，魚のショー、コアラのショー、象のショーなどを無視できました。なぜなら，これらのショーを含むスケジュールは，別のショーを選ぶことで，見られるショーの数が同じかより多いスケジュールを構成できるからです。
    • アルゴリズムをより効率化するもう一つの戦略は，問題を独立した部分，つまり部分問題に分解することです。コンピュータは異なる入力に対して同じ処理を繰り返し行うのが得意なので，独立した部分問題に適用できるアルゴリズムを見つけることは実現的な戦略です。
    • 問題の解法の説明でも，問題を独立して解決できるより小さな部分に分解しています。
    • 一般的に，特定の期間における複数のショーから見ることができる最大数を選ぶ処理は，活動選択問題ｙａインターバルスケジューリング問題と呼ばれます。大規模な工場でのプロセス管理や単一のコンピュータでの多くのプログラムの実行において，数千または数百万の活動を含む活動選択問題が生じるかもしれません。情報学では，総当たり探索を使わずにこれらの問題を解決するさらに高度なアルゴリズムが開発されています。
    • この問題では，最大の解を見つけるための戦略を開発する必要があります。ショーの開催時間の重複を分析し，最適な解に含めるべきショーと考慮しなくても良いショーの見分かることで実現できます。

  2023-新生物リッカ-解説

  • 考案国：カナダ
  • 正解
    • ちょうど2本のうでを持つリッカは，必ずちょうど2本の足がついています。
  • 説明
    • 答えは「ちょうど2本のうでを持つリッカは，必ずちょうど2本の足がついています。」です。
    • 「リッカが2本のうでを持っている場合，2本の足がついている」というのはまちがっています。6枚目の写真には，2本のうでと4本の足を持つリッカが写っています。
    • 「リッカは必ず歯を持っています。」というメモは正しいかもしれません。6枚の写真に写っているリッカは全部歯がついています。
    • 「羽を持っているリッカもいれば，羽を持っていないリッカもいます。」というメモは正しいです。2枚目の写真には羽を持つリッカが写っています。
    • 「リッカは「つの」か「三つ目」のどちらかを持っていますが，「つの」と「三つ目」の両方を持ってるリッカはいません。」というメモは正しいかもしれません。1枚目，2枚目，5枚目，6枚目の写真には，角を持ち「2つだけ」目を持つリッカが写っています。残りの写真（3枚目と4枚目）には，角のない3つ目のリッカが写っています。
  • 実際のコンピュータでは
    • 　ビーバーはかせは，特徴を探すことでリッカをみつける方法を研究しています。コンピュータも「比較」と呼ばれるプロセスで特徴を見つけることができます。現在では、機械学習と呼ばれる方法で，たくさんのデータを自動的に，短時間で比較することができます。ビーバーはかせと同じように，コンピュータが間違った結論を出すこともあります。よりたくさんのデータ，コンピュータに学習させることで，コンピューター間違いを修正しすることができます。
    • データの中で繰り返し現れるパターンや規則性を見つけ出すことは，情報科学ではパターン認識と呼ばれています。パターン認識は，機械学習や人工知能で使われており，コンピュータがデータから学習，予測や決定をすることを可能にします。たとえば，画像認識では，パターン認識技術は画像内の物体をみつけ，分類するのに使われています。言葉の処理では，パターン認識によってコンピュータは文の構造を理解し，内容を推測，人間が書いたようなテキストを生成することもできます。

  2023-ニンジンの種まき-解説

  • 考案国：スロバキア
  • 正解
    • 
  • 説明
    • ウサギは，与えられた動作順にジャンプするには，左から3番目の丘からスタートしなければなりません。一度右にジャンプし，その後3回左にジャンプする必要がありますが，左から３番目の丘以外の場所からスタートすると，端から外れてしまうからです。
      
    • 最初の２つの動作
      
      の後には，うさぎは一番右の丘に種をまくことになります。
      
    • それに続く２つの動作
      
      後には，うさぎは右から二番目の丘に種をまきます。
      
    • 続く３つの動作
      
      で，一番左の丘に種をまきます。
    • したがって答えは次のようになります
      
  • 実際のコンピュータでは
    • これはアルゴリズム的思考を問う問題です。コンピュータは，ロボットのウサギを制御するのと同様の方法でプログラムされています。この問題では，ロボットの動作（コマンド）は（絵の描かれた）ブロックを使用して指定されます。動作（コマンド）の意味とその順序を理解して，プログラムの実行結果を考える必要があります。
    • ロボットのウサギの初期位置を見つけるためには，与えられた命令の順序をたどりながら，与えられた条件（ウサギがたねを丘に置く）をよく観察する必要があります。プログラムトレース（実行の観察）はプログラミングの重要な活動です。プログラムのバグを探すだけでなく，うまく動作するプログラムをつくるためにも使用されます。

  2023-ビーバーの散歩-解説

  • 考案国：日本
  • 正解
    • 
  • 説明
    • ビ太郎は以下の場所で写真を撮りました。
      
    • 最初の写真撮影スポットでビ太郎の北向きだったので，最初の写真では右側に家があるはずです。
    • 2番目の写真撮影スポットではビ太郎は南向きだったので，２番目の写真では左側に家があり，右側には木があるはずです。
    • 3番目の写真撮影スポットではビ太郎は西向きだったので，写真の風景は右側に木があるはずです。
    • したがって，正解は です。
  • 実際のコンピュータでは
    • タートルプログラミングやタイルベースのプログラミングなどのロボットプログラミングは，子ども向けの初歩的なプログラミングの教材として使われています。
    • ロボットの状態を理解し，ロボットの視点を想像することは，基本的なロボットプログラミングにとって不可欠です。
    • この問題は，学習者がロボットの視点からの右と左の区別を含め，ロボットの方向を正確に管理することを学べるように意図されています。
• B

  2023-ひみつの手紙-解説

  コンテスト時の問題文中には，開いている手紙に書かれた数の合計に関する情報が，スパイが手紙を１通開ける前の状態のみが含まれており，スパイが手紙を１通開けた後の状態が記載されていませんでした。
  そのため，十分な情報がないため，開けられた手紙を特定することはできない状態での出題となっていました。

  参加された皆さまには，ご迷惑をおかけして大変申し訳ありませんでした。
  今後は，このようなことがないように再発防止に努めます。

  なお，現在掲載している問題は，スパイが手紙を１通開けた後の状態を追記しております。

  • 考案国：フィリピン
  • 正解
    • 13
  • 説明
    • 偶数に偶数を加えても偶数のままです。合計が偶数から奇数に変化している場所があるので，スパイが開けた手紙に書かれている数は奇数です。
    • まず，列（たての並び）に注目します：
      • C2列とC4列の開いている手紙に書かれている数の合計は偶数であり，これは警備員の記憶と一致しています。スパイによって開かれた手紙は奇数が書かれた1通だけなので，スパイによって開かれた手紙はC1列またはC3列にあることがわかります。
      • C3列とC4列の開いている手紙に書かれている数の合計は偶数であり，これも警備員の記憶と一致しています。スパイによって開かれた手紙は奇数が書かれた1通だけなので，スパイによって開かれた手紙はC1列またはC2列にあることがわかります。
      • {C1列，または，C3列} と {C1列，または，C2列} の両方に含まれているのは C1列だけなので，スパイによって開かれた手紙はC1列にあることがわかります。
    • 今度は，行（横の並び）に注目します：
      • R2行とR4行の開いている手紙に書かれている数の合計は奇数であり，これは警備員の記憶と一致していません。したがって，スパイによって開かれた手紙がR2行またはR4行にあることが分かります。
      • R3行とR4行の開いている手紙に書かれている数の合計は奇数であり、これも警備員の記憶と一致しません。したがって，スパイによって開かれた手紙がR3行またはR4行にあることが分かります。
      • {R2行,または，R4行} と{R3行，または，R４行}の両方に含まれるのはR4行だけなので，スパイによって開かれた手紙はR4行にあることが分かります。
    • 上記の考察により，スパイによって読まれた手紙はC1列とR4行にあることが特定されます。
      
  • 実際のコンピュータでは
    • 　この問題は，エラー訂正の概念を学ぶための問題です。デジタルデータは本質的にビットのシーケンス，つまり1と0の列でできています。デジタルデータがネットワークで送信されるときには，電気ノイズや改ざんなどよってデータが破損する可能性があります。DVDに保存されたデータなども，ディスクが傷ついた場合などに一部のデータが破損することがあります。したがって，破損したことを検出（エラー検出）し，破損したデータを訂正する（エラー訂正）仕組みが必要です。

  2023-ビバ子の森の家-解説

  • 考案国：ドイツ
  • 正解
    • 
  • 説明
    • ビバ子の森の家を見つけるには，3枚の地図からの情報をあわせる必要があります。ビバ子の森の家は森林地帯にあり，川に近い必要がありますが，これは左上にある家にのみ該当します。地図を重ね合わせると，簡単にわかります。
      　
  • 実際のコンピュータでは
    • もし森，川，家に関する情報が1枚の地図に表示されていれば，探している家を簡単に特定できるでしょう。
    • 地理情報システム（GIS）では，さまざまな空間情報が集められ，地図上に表示されます。GISは地理データを視覚化し分析するために役立ちます。GISの助けを借りて，災害対策の担当者はたとえば避難計画のための情報をまとめることができます。
    • 異なる画像情報を持つ複数のレイヤー（層）とその重ね合わせの原理は，グラフィックスプログラムでもよく知られています。重ね合わせるときに気をつけなければならないことは，重ね合わせる順序です。例えば，ビバ子の地図では，家が森に隠れないように，最上層のレイヤーにする必要があります。

  2023-植物の相性-解説

  • 考案国：オーストリア
  • 正解
    • 
  • 説明
    • まず，にんにくの隣には相性の悪い豆を植えることはできないので，豆はにんにくの植え込みの隣にならない４箇所に植えるようにします。
      
    • 次に，豆と相性の悪いトマトを豆の隣に植えないようにしないといけません。豆の隣を避けるようにすると，トマトを植える３箇所が決まります。
      
    • 残っているのは3つの花と2つのトウモロコシです。どちらも豆との相性はよく，トマトは花（ミツバチを引き寄せる）との相性が良く，トウモロコシとは相性が悪いです。そのため，トマトの隣には花を植えます。最後の2つのマスには、トウモロコシを植えます。
      
  • 実際のコンピュータでは
    • この問題は多くの方法で解くことができます。全ての条件を満たすまで各植物を全ての植え込みに配置してみるブルートフォース（総当たり/しらみつぶし）アプローチを使用することもできますが，この方法は多くの時間がかかります。代わりに，問題をより分析し，選択の数を減らす条件を探します。
    • 植物間の関係は無向制約グラフで表現できます。二つのノードがエッジ（辺）で接続されているのは，それらが良い共栄作物である場合（緑の実線），もしくは相性が悪い作物である場合（赤い点線）です。
      
    • この問題は，決定問題の1つとして知られる組み合わせ最適化問題でもあります。多くの組み合わせ最適化問題は，グラフ問題としてモデル化し，グラフ問題の最適化，what-if シミュレーション，制約充足問題，グラフ分類，グラフ描画と可視化などで解決します。
    • 農家や他の園芸家は，庭に植生を植える際に共栄作物の情報を使用します。この情報は，庭の生産を最適化するための情報に基づいた決定を下すのに役立ちます。例えば，豆は窒素を提供することでトウモロコシに利益をもたらし，トウモロコシの植物は安定性を提供することで豆を助けます。

  2023-お宝からの信号-解説

  • 考案国：スロバキア
  • 正解
    • 5
  • 説明
    • ゲームボード上のマス「C」と「F」が正確であるかを確認するために，マス5までの距離を確認していきましょう。矢印の方向に移動したときにマス5までの距離が増加した場合は「F」が記され，マス5までの距離が減少した場合は「C」がそのマスに記されることが分かります。得られた信号のシーケンスは報告された結果と一致しています。したがって，宝はマス5の下に置かれています。
      
      以下では，他のマスの場合には「お宝の信号」に矛盾が生じてしまうことを検証してみます。
    • マス1、2、または4に埋められた宝の場合：
      もし宝がマス1，2，または4のいずれかの下に埋められていた場合，行4と列2の「F」という文字は「C」でなければなりません。なぜなら，そのマスは宝（これら3つの場所すべて）に近いため，そこから来たマス（行4，列3）よりも近いからです。
      
    • マス3に埋められた宝の場合：
      もし宝がマス3の下に埋められていた場合，行2と列6のマスは「F」でなければなりません。なぜなら，そのマスはプレイヤーがスタートしたマス（つまり、行1と列6）よりも宝から遠いからです。
      
  • 実際のコンピュータでは
    • 強化学習は，機械学習の手法の一つで，知的エージェントが環境内で取るべき行動について，報酬を最大化するアルゴリズムです。強化学習システムの基本的な要素には，エージェント，それが相互作用する環境，決定を下すために従う方針，そして行動を取った後に受け取る報酬信号が含まれます。報酬信号を評価するために，評価関数が特定の状態の「良さ」を評価します。
      このタスクでは，移動後のゲームボード上の新しい位置が環境を表し，検出された距離から得られた信号が報酬信号として機能します（'C'は正の報酬を，'F'は負の報酬を示します）。次のステップに最適な決定を下すことで，ビ太郎はエージェントとして機能します。彼は宝が含まれている可能性のあるマスを検討する必要がありますが，これは評価関数と考えることができます。
    • この問題でのマス間の距離は，マンハッタン距離（タクシー距離とも呼ばれる）によって測定され，プレイヤーは水平または垂直にのみ移動できます。自動運転は強化学習の応用例です。予測不能な環境でうまく機能するために，自動運転システムは車両の経路計画や運動予測など，多くの認識と計画のタスクを実行する必要があります。車両の経路計画には，異なる時間的および空間的スケールを考慮した決定を下すためのさまざまな低レベルおよび高レベルの方針の使用が含まれます。一方，運動予測には，歩行者や他の車両の動きを予測し，現在の環境状態に基づいて状況がどのように進化するかについての洞察を提供することが含まれます。
• C

  2023-荷下ろし-解説

  • 考案国：インド
  • 正解
    • 7
  • 説明
    • 荷降ろしの順序は1, 2, 3, 4, 5, 6, 7, 8, 9, 10です。最初のラウンドでボックス1と2が一緒に降ろされ，次に3と4が一緒に，次に5，次に6，その次に7と8が一緒に，次に9，最後に10が降ろされます。これで7ラウンドです。
    • 別の解法として，次に荷下ろしをするコンテナの番号が列車内でそれより左に来る場合，追加のラウンドが必要だという一般原則に気づくかもしれません。例えば，3が2の左に現れる場合，2を降ろすために3はスキップされ，3をクレーンの下に持ってくるために追加のラウンドが必要になります。与えられた課題では，順序が狂っているペアは(2,3), (4,5), (5,6), (6,7), (8,9), (9, 10)であり，6ラウンドの追加が必要なので，合計7ラウンド，と求めることができます。
  • 実際のコンピュータでは
    • 列車内で次に大きい数がそのボックス番号の左にある場合，これを「逆順」と呼びます。このような逆順ごとに，追加のラウンドが必要です。逆順の数を数えると答えが得られます。望ましい順に対して逆順を考える方法には多くの応用があります。例えば，バブルソートなどのいくつかのソートアルゴリズムでは，逆順の数は与えられたシーケンスをソートするために必要な交換の回数を教えてくれます。他の例として，オンラインショップで２名のユーザが商品を好みの順にランク付けした場合，彼らのランキングの逆順の数によって，彼らの好みがどれだけ一致しているかを調べることができます。これはオンラインショップによって「似たような」ユーザを特定し，製品の推薦を行うために使用されます。
    • この問題を解決するためにアルゴリズム的思考が必要です。荷降ろし手順のステップのシーケンスが与えられ，荷降ろしがどれだけ時間がかかるかを決定するためにこれらの手順に従う必要があります。または，解法で見たように，分解と論理を組み合わせたこのタスクの解決方法もあります。

  2023-ウォーキング・ホリデー-解説

  • 考案国：アメリカ
  • 正解
    • 6
  • 説明
    • 
    • 問題を分解して考えることで考えてみましょう。まず，ビバ子はBとCに滞在しなければならないことに気づきます。これらの2つの場所の距離は２であり，ビバ子が1日で歩ける最大の距離だからです。これにより，この前後の二つのセクションを2つの小さな問題として考えることができます。
    • まず，スタートからBまで行く方法について考えます。方法は2つあります（ルート1とルート2に示されている方法）。したがって，Cへの可能なルートも2つということになります。
    • 次に，Cから終点までに行く方法について考えます。これについては，次の3つの可能性があります。
      • C → D → E → End
      • C → E → End
      • C → D → End
    • このようにして，前半で２通り，後半で３通り，合計で2 x 3 = 6つの可能なルートがあることがわかります。
  • 実際のコンピュータでは
    • 説明にあるように，この問題は2つの小さな問題に分解して解決することができます。同様の大きな問題では，動的計画法での解決策が採用されます。アルゴリズムが問題を非常に小さな部分問題に分解し，小さな問題の解決策を使用して大きな解決策を作り出す戦略です。
      
    • タート，A，B，C，D，E，エンドという場所に番号を付けると，各場所に到達する方法が何通りあるかの表を作ることができます。

      場所	到達方法
      スタート	1
      A	1 (スタートから到達できる)
      B	1 + 1 = 2 (スタートから直接来るかAを経由する)
      C	2 (Bから来る必要がある)
      D	2 (Cから来る必要がある)
      E	2 + 2 = 4 (BかCから来る)
      End	2 + 4 = 6 (DかEから来る)

    • 説明でみたように，一つ一つ課題を分割して上記の表を埋めていくことを動的計画法と呼びます。これは，人間が解決するのに時間がかかるような大きな問題に対しても解決策を見つけることができる，コンピュータが得意なアルゴリズムです。

  2023-オガム・コード-解説

  • 考案国：アイルランド
  • 正解
    • 
  • 説明
    • 答え見つけるためのさまざまな方法がありますが，以下では，1つの例を示します。
    • 最初のステップは，単語をどの方向で読むかを解読することです。左から右へ（または右から左へ）ではないことは直感的にわかります。なぜなら，その場合，単語は4文字で，7つの単語に鳴るはずだからです。各ボックスの位置も意味をなさなくなります。そこで，まずは上下の4つの文字と，単語の最初と最後の文字を比較します。3つの単語が同じ文字（S）で終わるため，それらは上で終わらなければならないので，読み方は下から上，ということがわかります。ここまでわかったら，各単語を個別に分析します。
      • BANANASは3つの同じ文字「A」を持つ唯一の単語であり，3番目の画像も3つの同じ文字を持っているので，それはBANANASでなければなりません。したがって，文字Aは単一の長い線であることがわかります。
      • ORANGESは「A」を持つ他の唯一の単語です。残った唯一の画像には単一の長い水平線がありますので，2番目の画像は「ORANGES」でなければなりません。
      • 残りの単語はLETTUCEとBERRIESです。
    • ORANGESとBANANASの両方が「S」で終わります（右に4つの水平線）。4番目の画像も同じ文字で終わるので，それはBERRIESでなければなりません。 したがって，LETTUCEは最初の画像ということになります。
    • 最終的な各文字の解釈を以下に示します。
      
  • 実際のコンピュータでは
    • この問題は暗号解読の簡単な例を扱っています。暗号解読は，暗号を「解読」する方法に関する研究です。暗号解読は，暗号を複合するのに必要な「鍵」がない状態で，暗号化されたメッセージを解読するのに使用されます。暗号解析家と呼ばれる専門家がメッセージを解読しようとします。その際、彼らは隠されたメッセージにおそらく含まれているであろう単語についての知識を使用します。
    • パターン認識： この問題を解くには，単語と絵の間のパターン（同じ文字の繰り返しなど）を見つけることが重要です。
    • 分解： この問題は，解読できる部分に分割することで解くことができます（例えば，一度に1つの文字を見つけ出す）。部分的な解答を組み合わせることで，最初は複雑だった問題を解くことができます。
    • 表現： この問題では，文字がどのように異なる記号や絵で表されるかを理解する必要があります。

  2023-ジューススタンド-解説

  • 考案国：ブラジル
  • 正解
    • 4
  • 説明
    • 追加のジュースカートの最適な場所を見つけるために，まず，既存のジューススタンドから１つか2つの道路を歩いて行ける交差点をすべて除外します。
      
    • 除外すると，2つの通りを歩いてジューススタンドにたどり着けない場所は，4つの交差点のみになり，問題は単純になりました。交差点1, 2, 3 にジュースカートを配置しても，1つか2つの通りでジューススタンドに到達できない場所がまだいくつか残ります。交差点4にジューススタンドを配置すると，残りの各交差点が最大で2つの通りの距離になります。
  • 実際のコンピュータでは
    • グラフは，地図上の通り，人々の関係，閉じたシステム内の状態，階層的に整理された単語など，さまざまな文脈に適用することができます。この問題は，グラフ理論での「支配集合問題」を扱っています。この理論は，この問題の例のように，最大2回の移動で全ての市民や場所にサービスを提供する公共交通網をどのように構築するかといった，実世界の問題に適用されています。

（カデット問題に戻る）