SeniorAnswer2017

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

A
2017-おばあさんのジャム-解説
- 考案国：ロシア
- 正解
  - 次の2種類の正解パターンがあります。
    
    　
  - 3人の役割は入れ替わっても良いので、上の正解パターンには３つの正解が、下の正解パターンには６つの正解が、つまり、合計で9つの正解があります。
- 説明
  - 1個の瓶詰を作るには、3分と2分と1分で合計6分かかります。使える時間は3人で10分間の合計30分ですので、5個より多くは作れません。
    そして、瓶を洗う前にジャムを入れることはできませんし、ジャムを入れる前に蓋をすることはできません。
- 全員が次の方針で作業をすることを考えましょう。
  - 洗った空（から）の瓶がないときは、瓶を洗う
  - 洗った空の瓶があるときは、ジャムを入れる
  - ジャムの入った蓋の開いた瓶があるときは、蓋をする
- この方針で作業すると、上の正解を作れます。
- 下の正解は、瓶を2個洗った2人うち一人が、瓶にジャムを入れる作業の前に蓋をした場合です。
  瓶を2個洗い終わった時点では、ジャムが入った瓶は1つしかないので、瓶にジャムをいれる作業の前に蓋をできるのは1人だけです。
- 3人がうまく協調しないと、3人で10分間で5個の瓶詰を作れません。　
  - たとえば3人が独立して仕事をすると、次の図のように10分間で3個しか作れません。
    
    　
    2人が担当する仕事を2種類ずつに減らしてしまうと、やはりうまく行きません。次の図のように、一番下の役割の人が2番目と3番目の蓋をする作業をしようとすると、まだジャムが入っていないので作業できず、10分間で3個しか作れません。
- 実際のコンピュータでは
  この問題は、作業計画問題と作業の並列性を扱っています。
2017-新曲-解説
- 考案国：イラン
- 正解
  - 「木曜日」
- 説明
  - TomとTedとKimは1日目に、AnnaとJaneは2日目に、Joeは3日目に曲を買えます。
    （火曜日の状態）
    
    （水曜日の状態）
    
    木曜日には、全員が曲を買いました。
  - 実際のコンピュータでは
    この問題は、SNSで影響が広がる様子を扱っています。ある情報が広がるかどうかは周りの友人たちのしきい値（ある一定の割合を超えているかどうか）に影響されます。このような研究はSNSにおける商品広告などで利用されています。
2017-迷子の赤ちゃんビーバー-解説
- 考案国：韓国
- 正解
  - 「3」
- 説明
  - 迷子の赤ちゃんビーバーがいる可能性のある場所は、3箇所です。
    赤ちゃんビーバーは、お母さんビーバーに「岩は見えない」と言いました。そこで、岩との距離は5以上あります。そこで、下の図の灰色の部分には赤ちゃんビーバーはいないことがわかります。
    
    次に、赤ちゃんビーバーは、「1つの木までの距離が4」「もう1つの木までの距離が2」と言いました。そこで、それぞれの木までの距離が「4と2」または「2と4」であるという条件で考える必要があります。
    ここでは説明のために、ブロックの位置を（左から何個目、上から何個目）のように書くことにします。
    そうすると、「(1,2)の木と(5,4)の木までの距離が2と4であり、岩までの距離が5以上」は次のブロックになります。
    
    また、「(1,2)の木と(5,4)の木までの距離が4と2であり、岩までの距離が5以上」は次のブロックになります。
    
    これらのことから、赤ちゃんビーバーがいる可能性があるブロックは3つであることがわかります。
  - 実際のコンピュータでは
    情報科学では、データの位置を縦横のブロック（グリッド空間）で表すことがあります。
    この問題で扱ったような最短の距離はマンハッタン距離と呼ばれています。
2017-本の整理-解説
- 考案国：イタリア
- 正解
- 説明
  - 正解はDです。ジャックは5冊、スーは4冊本を置くことができます。
    次の表はジャックとスーがどのように本を置いていったかを本に書かれた番号で表しています。
  - 実際のコンピュータでは
    ジャックとスーによって採用されたやり方は、それぞれファーストフィット方式とワーストフィット方式と呼ばれる2種類のメモリ管理方法に相当します。
B
2017-ファイル-解説
- 考案国：オーストリア
- 正解
  - 「「アン」が出て来る物語の一部も「アンの物語」のフォルダから消えてしまう。」
- 説明
  - 最初に「アン」という文字が含まれるファイルをコピーしたときに、「アンの物語」のフォルダには、「アン」だけが含まれるファイル（図の青色）だけでなく、「アン」と「ジョアン」が両方とも含まれるファイル（図の緑色）が入った可能性があります。「ジョアン」が含まれるファイルを消すと、「ジョアン」だけが含まれるファイル（図の黄色）だけでなく、このようなファイル（図の緑色）も消されてしまうことになります。
  - 実際のコンピュータでは
    ファイルの検索は重要な作業です。ファイルは、ファイル名かファイルの中身で検索します。この問題のように、単純な操作でも誤ってファイルを消してしまうことがあります。機械的な操作だけに頼らずに、人の目でも確認しながら作業を行うことは有用です。
2017-迷路脱出-解説
- 考案国：スイス
- 正解
- 説明
  - 次の動きを2回繰り返すと出口に行くことができます。
    　
  - 実際のコンピュータでは
    プログラムは一連の命令で構成され、ときには一連の命令を繰り返す必要があります。これを簡単に可能にするために、プログラミング言語には「ループ」と呼ばれる特別な命令が提供されます。ループに入れられた命令は、開発者が決めた回数だけ繰り返すことが出来ます。
2017-ロボット-解説
- 考案国：スロバキア
- 正解
- 説明
  - ロボットの進み方は次のとおりです。
    　スタート：
    　従うルール：　結果：
    　従うルール：　結果：
    　従うルール：　結果：
    　従うルール：　結果：
    　従うルール：　結果：
    　従うルール：　結果：
    　従うルール：　2回目の結果：
    　従うルール：　結果：
    ここで、ロボットが正方形の外に出たので止めます。
  - 実際のコンピュータでは
    コンピュータ科学では、動作する計算モデルを明らかにすることは重要なことです。
    この問題はチューリングマシンと呼ばれるとても有名なモデルにとても似たモデルを定義しています。
2017-バイクファン-解説
- 考案国：ドイツ
- 正解
- 説明
  - Cだけが成功することができるコースです。
    平坦な区間で加速（+）、減速（−）、加速（+）とするとゴールする時に時速を0kmにすることができます（+ - -）。あるいは、（- + -）または（- - +）でもうまくゴールすることが可能です。
    　
    他のコースでは実行できません：
    ・コースA：2つの平坦な区間でスピードを上げたとしても、4つ目の区間で動かなくなります
    ・コースB：平坦な区間で減速したとしても、スピードが速いままゴールしてしまいます
    ・コースD：最後の区間でバイクのスピードが上がり、その後減速することができないため、時速を0kmにしてゴールすることはできません
    　
  - 実際のコンピュータでは
    この問題の加速を開きカッコ「（」、減速を閉じカッコ「）」と考えると、「数式などで、開いたカッコがきちんと閉じられているか」という問題と同じように考えることができます。
    たとえば、「(3+2)」や「(4+(3-2))」は正しい式ですが、「(3+2」や「3+2)」「(4+(3-2)」「(4+3-2))」は正しい式ではありません。
C
2017-カラフルな建物-解説
- 考案国：日本
- 正解
- 説明
  - アリスとボブとクリスが見える色を整理すると、次の表のようになりました。
    水青緑オレンジピンク赤黒黄
    アリス ○ ○ ○
    ボブ ○ ○ ○
    クリス ○ ○ ○
    あなた A C C 中央 A
    ここから、次のことがわかります。その内容を下の図に表しました。
    ・ボブは、アリスと同じ色（黒）を見ていて、クリスとも同じ色（赤）を見ています。よって、ボブはアリスとクリスの間（図の左上）にいることがわかります。
    ・アリスとクリスの場所はボブの隣であればよいので、アリスを右上、クリスを左下にしてみました。実際はアリスが左下、クリスが右上かもしれません。
    ・アリスから見えている色のうち、ボブとアリスが見ている色（黒）以外の色（水か黄）が、あなたからも見える色の候補です。（表のAの部分）
    ・クリスから見えている色のうち、ボブとクリスが見ている色（赤）以外の色（緑かオレンジ）が、あなたからも見える色の候補です。（表のCの部分）
    ・選択肢の候補から、「Aの色、ピンク、Cの色」または「Cの色、ピンク、Aの色」という並びを探してみましょう。
2017-サイコロ-解説
- 考案国：マレーシア
- 正解
  - 「4の面」
- 説明
  - 正解は「4の面」です。
    これからおこなう1つの方法は、サイコロの動きに合わせてすべての6つの面の位置の追跡し続けます。もしもそれ以外の3つを簡単に判別できるのなら、追跡を3つの面のみにすることで複雑さを少なくすることができます。
    例えば、右側、正面と上の位置にある3, 5, 6の面の始めの位置をメモすることができます。一つ一つ最後のマスまで、サイコロの動きに合わせて3つの面の追跡を続けます。7回転がした後、どれがサイコロが下になったのかがわかります。
    ステップ動作 3の位置 5の位置 6の位置
    右正面上
    1 ↑ 右上背面
    2 ↑ 右背面下
    3 ↑ 右下正面
    4 → 下左正面
    5 → 左上正面
    6 ↓ 左側面下
    7 ← 上側面左
    上に「3の面」があるので、下になっているのは「4の面」です。
  - 実際のコンピュータでは
    この問題では、それぞれのステップで情報の一部のみを追跡することによって問題を解決しています。
    このような方法を使うことで、メモリの使用率と複雑さを減らすことができます。コンピュータのプログラムでは、このような工夫が多く使われています。
2017-画像圧縮-解説
- 考案国：韓国
- 正解
  - 「(111(1(1011)11))」
- 説明
  - 全体を縦横半分ずつの4つの領域に分け、必要に応じてそれぞれの領域をさらに縦横半分ずつの4つの領域に分けて行きます。
  - 実際のコンピュータでは
    四分木は広い平面を簡潔に表現するために使われています。問題の例では、最初に全体を4つの領域に分けたときに、3つの領域（左上と右上と右下）を「111」というわずか3文字で簡潔に表現できています。また、画像全体を見ると、最初は画像を表すために64個の数字が必要でしたが、圧縮後は11個の数字と6個のカッコの記号の計17個の文字で画像を表現できています。
2017-数字の区別-解説
- 考案国：ロシア
- 正解
- 説明
  - 4つの線分を使うと、 2x2x2x2 で 16 種類の形をつくれます。ですが、4つの線分だけでは、10種類の数字 (0 .. 9) を曖昧さなく区別することはできません。そして、正解は P の形だけになります。考え方を順に見ていきましょう。
    - (1) 0 と 8 は、１つの線分が異なるだけです。そのため、0 と 8 を区別するには、この線分が必要です。
      この線分を使っているかどうかで、0 から 9 の数字を {2, 3, 4, 5, 6, 8, 9} と {0, 1, 7} の２つのグループに分けます。
    - (2) 1 と 7 も、１つの線分が異なるだけです。そのため、1 と 7 を区別するのは、この線分が必要です。
      この線分を使っているかどうかで、{2, 3, 4, 5, 6, 8, 9} と {0, 1, 7} をそれぞれ２つのグループに、つまり、合計４つのグループに分けます: {2, 3, 5, 6, 8, 9}, {4}, {0, 7},{1}
      1 と 4 は、1つだけのグループになったので、これらの２つの線分を使うだけで、1 と 4 は確認できます。
    - (3) 他にも、１つの線分だけ異なる数字の組があります。8 と 9 です。8 と 9で異なる線分も必要です。同じように、この線分を使っているかどうかで、グループを分けると、{2, 6, 8}, {3, 5, 9}, {4}, {0}, {7}, {1} となります。
    - (4) 6 と 8 も、１つの線分が異なるだけです。そのため、6 と 8 を区別するには、この線分が必要です。この線分を使っているかどうかで、グループを分けると、{2, 8}, {6}, {3, 9}, {5}, {4}, {0}, {7}, {1} となります。
    - このように、4 つの線分だけでは、10種類の数字 (0 .. 9) を曖昧さなく区別できないことがわかります。
    - (5) 3 と 9 も、１つの線分が異なるだけです。この線分は、2 では使われていませんが、8 には使われているので、2 と 8 も区別できます。
    - このように考えていくと、(1)から(5)の線分を使うことで、すべての数字を区別できることが表からわかり、正解の P の形が得られます。
      　
      
      　
      線分 1 2 3 4 5 6 7 8 9 0
      (1) o o o o o o o
      (2) o o o o o o o o
      (3) o o o o
      (4) o o o o o o o o
      (5) o o o o o o
  - 実際のコンピュータでは
    パターン認識アルゴリズムは、一般に、統計的変動を考慮して、様々な入力に対して妥当な答えを提供したり、入力を「おおよそ近い」ものに対応させたりすることを意図しています。
    パターン認識は、データ中のパターンや規則の抽出に焦点を当てた機械学習の一分野です。
    認識手法の一つに、対象を一意に識別できる特徴を抽出するものがあります。
    コンピュータビジョンは、現在、活発に発展している情報技術の一分野です。