シニア問題解説(高校２年生・３年生)

• A

  2021-プレゼント2-解説

  • 考案国：ドイツ
  • 正解
    
  • 説明
    • 同じプレゼントを欲しいビーバーが2匹いますので、全員に一番好きなプレゼントを渡すことはできません。まず、一番好きなプレゼントが重なっていない3匹については、そのプレゼントを渡すことにしましょう。
      次に、一番好きなプレゼントが重なっている2匹について考えます。2匹を見ると、二番目に好きなプレゼントは、1匹はまだ渡されていませんが、もう1匹はすでに他のビーバーに渡されていることがわかります。
      そこで、「2番目に好きなプレゼントが他のビーバーに渡されている」ビーバーに一番好きなプレゼントを渡し、「2番目に好きなプレゼントがまだ渡されていない」ビーバーに二番目に好きなプレゼントを渡すことで、すべてのビーバーが一番好きなプレゼントか二番目に好きなプレゼントを受け取ることができました。
  • 実際のコンピュータでは
    • この問題では、ビーバーたちは一番目と二番目の希望を言いました。他のプレゼントは、すべて三番目と考えることができます。
    • できるだけ一番目の希望をかなえるか、できるだけ二番目の希望をかなえる組み合わせが他にないとき、その組み合わせは最適になります。
    • コンピュータ科学では、このような組み合わせ問題を「最大マッチング問題」と呼んでいます。組み合わせ問題にはいろいろなものがありますが、中には「安定した結婚問題」というものがあります。面白そうですよね。ぜひコンピュータ科学を学んでみてください！

  2021-停電-解説

  • 考案国：ハンガリー
  • 正解
    
  • 説明
    • まず、停電している家を見ると、Eにつながる2本の電線と、Cにつながる3本の電線はすべて切れていることがわかります。1本でもつながっていれば、EやCは停電になりません。
    • 次に、停電していない家を見ると、その家には電気が届いていることから、風車からAまでの電線は切れていません。Hにつながる電線も切れていません。Fにつながる電線は、Eとつながる電線は切れているので、Gとつながる電線は切れていません。
    • 残りの停電していないB, G, Dの家は、複数の電線でAとつながっています。そのため、たとえばBの家は、Aとつながる電線が切れても、Gとつながる電線から電気をもらえます。このように、A,B,G,D,Aをつなぐ電線は、どれか1本が切れても停電しないことがわかります。
  • 実際のコンピュータでは
    • コンピュータのネットワークでは、この問題の電線と同様に、多くの通信線で実現されています。通信線の中には、速度が遅かったり、過負荷だったり、あるいは完全に壊れていたりといったような、障害が発生することがあります。ネットワークの構造に冗長性を持たせることで、1箇所で障害が発生しても継続的に利用できるようになる工夫が行われています。
    • コンピュータの科学者は、ネットワーク構造を表現するために、「グラフ」という表記法を使います。グラフを扱うアルゴリズムは数多く存在します。例えば、ネットワーク構造を考えた上で、できるだけ効率的に障害のある線を発見することができます。
    • システムの故障（エラー）を修正することは、コンピュータネットワークだけでなく、ソフトウェア開発においても、コンピュータ科学者が頻繁に行う作業です。エラーを修正するためには、その原因を正確に特定する必要があり、この作業は通常、いくつかのステップで徐々に行われます。プログラマーの中には、プログラムに含まれるすべてのエラーやバグを見つけることはできないと考える人もいます。

  2021-出会い-解説

  • 考案国：リトアニア
  • 正解
    • 正解は4分です。下の図のように進むと最短で出会うことができます。（別解として、左下の自転車に乗ってから左側の自動車に乗ると、同じく4分間で出会うことができます）
      
  • 説明
    • では、3分以内に着けない理由を考えてみましょう。
    • 3分では、左側の自動車に着くことはできますが、走らせる時間はありません。そして、自動車の場所には右側にいる相手が3分で着くことはできません。結果として、自動車は使えないことがわかります。
    • 次に自転車を考えると、2人が自転車に乗るために1分かかり、残りの2分では自転車で会うことはできないので、やはり無理なことがわかります。

  2021-机-解説

  • 考案国：エルサルバドル
  • 正解
    • A を3回押して，B を4回押して，C を2回押す
  • 説明
    • 「A」ボタンを3回押すと、机1、2、3の高さがそれぞれ40、100、80になります。
    • 次に「B」ボタンを4回押すと、机2、3、4の高さはそれぞれ60、40、40になります。
    • 最後に「C」ボタンを2回押すと、机1、3、4の高さはすべて60ビーバー単位になります。
  • 実際のコンピュータでは
    • プログラムを作るときに、条件によってコンピュータに違う動作をさせたいことがあります。
    • そのようなときは、条件文を使うことで、条件によってコンピューターに異なる処理を行わせることができます。
• B

  2021-クモのキルト-解説

  • 考案国：カナダ
  • 正解
    
  • 説明
    • クモの巣を観察しましょう。すると、つながっている糸がわかります。
      ・1と3（3と1）
      ・1と5（5と1）
      ・1と6（6と1）
      ・2と4（4と2）
      ・2と7（7と2）
      ・3と6（6と3）
      ・4と6（6と4）
      ・4と7（7と4）
    • これらの場所に「米」の印が置かれているものが正解です。

  2021-サルのジャンプ-解説

  • 考案国：スロベニア
  • 正解
    • サルは、下の絵の紺色の8本の木に飛び移ることができます。
      
  • 説明
    • 公園の木をよく観察して、飛び移れる木に同じ色を付けていくと、上の絵のように6個のグループに分けることができます。
    • サルが黄色に塗られた木から出発した場合、すべての黄色の木に飛び移ることができますが、他の色の木には飛び移ることができません。
  • 実際のコンピュータでは
    • ある木から飛び移れる木に線を引くと、下の絵のような線を描けます。
    • 色を付けるほかに、線で結ぶことで、具体的な移動を表現することができます。
    • また、この絵のように点と線で情報を表現することで、問題をコンピュータに入力して解決することが可能になります。
    • 情報を点と線で表すことを「グラフ」にすると言い、問題をコンピュータで扱える形に整理することをモデル化と呼びます。
      

  2021-重ねられた果実-解説

  • 考案国：スロベニア
  • 正解
    
  • 説明
    • この問題は、次のように考えることができます。
      • まず、父はみかんだけが好きなので、一番最後に起きる父のために、みかんを一番下の箱に入れましょう。
      • 母は娘より前に起きるので、母が取るのは1番上か2番目の箱で、娘が取るのは2番目か3番目の箱です。息子の取る箱は1番目でも2番目でも3番目でも構いません。
    • これらを表にまとめると、起きる順の組み合わせは、次の3つの案が考えられます。
      
    • この表で2番目を見ると、息子と娘と母の可能性があるため、2番目の箱には3人全員が好きなものを入れる必要があります。それはりんごですね。
    • 次に、1番上の箱を考えると、残った果物はなしといちごですが、母はなしが嫌いなので、1番上の箱には、母と息子が好きないちごを入れる必要があります。そして、残った3番目の箱にはなしを入れましょう。
  • 実際のコンピュータでは
    • コンピュータ科学を学ぶときに、データの並ぶ順序を考えることは重要です。また、問題を解くためには、問題の背景情報を理解する必要もあります。この問題では、誰が最初に起きるのか正確にわからない状態でも、問題が解決できるように情報を整理する必要がありました。
    • この問題では、4個の箱の並びを考えるときに、スタックと呼ばれる考え方が使われました。スタックは「後入れ先出し」、つまり「最後に入れたものが最初に取り出される」データ構造です。スタックでは、1番上にあるものにしか取り出すことができません。1番上のものを取り除いて初めて、2番目のものが利用できるようになるのです。スタックはプログラミングの中でよく使われます。
    • この問題では、複数の条件を満たすように、果物の配置がうまくいくような解決策が求められました。しかし、問題にはいくつかの制約条件があり、すべての状況が発生するわけではありません。このような制約のある問題を解くのは、一般的には難しいことが多いです。そのためには、コンピュータプログラムを作成し、それを使っていろいろな組み合わせを試すことで、問題を解決するのが有効な場合があります。
    • コンピュータ科学やプログラミングでは、論理の考え方が重要です。このような論理を理解するための問題を解くことは、コンピュータやプログラムを学び始めたときに、よい練習問題になるでしょう。
    • 解説にあるように、すべての可能性を示す表を作ることは、与えられたデータを並び替えたり順序付けするための良い方法です。論理の組み合わせ（AND、OR、NOT）を使って、どのデータが有用かを判断するブール論理の考え方も役立ちます。この問題のような計算問題を解くことで、ELSE/IFのようなプログラミングにおける条件式も理解できるようになるでしょう。
    • 論理を理解して、論理的にプログラムの命令を実行して問題を解決する方法を理解した後は、多くの変数を持つ問題を解決するために、自分でコンピュータプログラムを書くことができるようになります。そして、スタックを処理するプログラムを書くこともできるようになるでしょう。

  2021-トルシェタイル-解説

  • 考案国：スロベニア
  • 正解
    
  • 説明
    • パッと見ただけでは、どのように考えてよいかがわからないかもしれません。それぞれのタイルについて、タイルの線がどこで交わるかを観察してみましょう。
    • 左のパターンでは、1本の連続した波状の線が見えます。ですから、この模様を作るタイルの線は、曲がっていて、タイルの端の直線のの真ん中でつながっている必要があります。
    • 曲線を使ったパターンは他に1つしかないので、そのパターンを作るためには、曲線を持ったもう1つのタイルを使う必要があります。
    • 残ったタイルのうちの1枚は、隅に暗い色がついています。残りの2つのパターンの角を見てみると、片方のタイルだけが同じ暗い色をしていることがわかります。
  • 実際のコンピュータでは
    • この問題では、考案者の人名にちなんで付けられたパターンを扱いました。
    • とてもシンプルな要素を組み合わせて複雑なパターンが作れることは、昔から人々が探求してきました。
    • このようなパターンは、数学やコンピュータ科学の分野で研究され、コンピュータゲームでは迷路や壁の模様などの生成に使われています。
• C

  2021-統一-解説

  • 考案国：フィリピン
  • 正解
    • 正解は24です。
  • 説明
    • 部族を統一する日数は、部族の村の数の合計になりますので、村の数の多い部族ほど、後に追加したほうがよいことがわかります。具体的に考えてみましょう。
    • まず、部族ごとの村の数は、少ない順に「緑2、青3、赤3、オレンジ4」です。そこで、少ない順に統一していくことを考えると、次のようになります。（統一後の色は、村の多いほうの色にしています）
      (1) 最初「緑2、青3、赤3、オレンジ4」
      (2) 緑と青を統一する。緑2＋青3→青5。「赤3、オレンジ4、青5」
      (3) 赤とオレンジを統一する。赤3＋オレンジ4→オレンジ7。「オレンジ7、青5」
      (4) オレンジと青を統一する。オレンジ7＋青5→オレンジ12。「オレンジ12」
    • かかった日数を合計すると、「5＋7＋12」で24になります。
  • 実際のコンピュータでは
    • この問題は、最適化問題のひとつです。最適化問題では、与えられた制約条件の中で、結果の値を最大化または最小化するための戦略を考えます。私たちの生活でも、最適化問題は、目的地までの最適な道を見つけるときなどに活用されています。
    • 最適化問題を解く方法のひとつに、貪欲アルゴリズムがあります。貪欲アルゴリズムでは、「各段階で最適な選択をすれば（局所的最適）、最終的に最適な結果（大域的最適）が得られる」という仮定を使います。今回の問題では、この仮定が成り立っていました。つまり、全体の日数を最小化するためには、それぞれの統一の日数を最小化しなければなりません。
    • 貪欲アルゴリズムは、すべての最適化問題に適しているわけではありませんが、多くの場合は時間内に正解または正解に近い値を求めることができます。

  2021-ビーバーソート-解説

  • 考案国：ドイツ
  • 正解
    • 「59～3600」
  • 説明
    • 60本の丸太を並び替えるためには、すべての丸太を調べるために、最低59回は動く必要があります。そこで、「0～30」と「6～70」は不正解であることがわかります。
    • また、丸太が逆の順番になっていた場合は、すべての丸太を左端に移動していく必要があるため、「30本目の丸太であれば、丸太の場所に行くために28回右に移動して、丸太を左端に移すために28回左に移動する」必要があります。これを3本目の丸太から60本目の丸太まで繰り返して行う必要があるため、全部で「2(1+2+...+58)」回の移動が必要になり、計算すると3481回の移動が必要です。そこで、「59～300」も不正解であることがわかります。
  • 実際のコンピュータでは
    • データを小さい順や大きい順に並び替える処理は、整列（ソーティング）と呼ばれ、コンピュータの中で便利に活用されています。並べるデータは、数値であっても構いませんし、人名のような文字列であっても構いません。
    • この問題では、ノームソートという2000年にイランのコンピュータ科学者が考案したアルゴリズムを扱いました。手順の考え方はシンプルで、「左端からデータを調べていき、大小順になっていないデータを見つけると、それを左のデータと比較しながら左端まで並べていく」処理を繰り返します。ソートされているデータに対しては、左端から調べていくだけなので早く処理が終わります。
    • アルゴリズムの速さは、データ数が増えたときにどれくらい遅くなっていくかで比較します。ノームソートは、データ数の二乗で遅くなることが知られています。

  2021-グループ分け-解説

  • 考案国：スイス
  • 正解
    • 消すべき線は、下の図のオレンジ色の線です。
      
  • 説明
    • ある2人が知り合いになると、その2人を結ぶ線は消えます。
      この問題では、線を1本消すことで、参加者を表すすべての点を2色で塗る必要があります。そのとき、同じ色の点が線で結ばれていてはいけません。
    • 正解のオレンジ色の線を消すと、下の図のように、すべての点を2色で塗ることができます。
      
    • 他に正解がないかを確かめるために、右上のオレンジ色の三角形の部分を考えてみましょう。外側の2本のオレンジ色の線は、どちらを消しても3色が必要になってしまいます。
      
    • 次に、下のほうにある五角形の部分を考えてみましょう。外側の3本のオレンジ色の線は、どれを消しても五角形の形は残るため、3色が必要になってしまいます。
      
    • 五角形について、ある点から始めて、時計回りに見ていくと、2つの色を交互に使う必要があります。しかし、点の数が奇数だと、最後の点が最初の点と重なるため、最初の色と同じになってしまいます。
    • そのため、「この1本の線を消せば、三角形と五角形が作られないようになる」ような線を考えれば、唯一の正解を考えることができるでしょう。

  2021-働く2匹のビーバー-解説

  • 考案国：リトアニア
  • 正解
    • 正解は23時間です。
  • 説明
    • 作業にかかる時間を合計すると46時間になります。2人で作業しますので、最短の時間は23時間より短くなることはありません。
    • 作業の分担は、いくつかの正解が考えられます。
      • 正解例(1)
        ビーバー１：　A(2)、C(5)、E(10)、H(6)
        ビーバー２：　B(3)、D(7)、F(9)、G(4)
      • 正解例(2)
        ビーバー１：　A(2)、B(3)、C(5)、F(9)、G(4)
        ビーバー２：　D(7)、E(10)、H(6)
  • 実際のコンピュータでは
    • この問題では、「取り組める作業のうち一番時間がかかる作業を行う」という作戦で進めると、作業の空き時間ができてしまい、23時間で終わる作業が32時間かかってしまうという例を見ました。
    • この問題では、この作戦は時間がかかってしまいましたが、他の問題ではうまくいくかもしれません。作業の最短時間を求めるアルゴリズムを考えることは簡単ではありません。確実なのはすべての作業の組み合わせを試してみることですが、作業が多いと計算だけで時間がかかってしまいます。

（シニア問題に戻る）