JuniorAnswer2018

ジュニア問題解説(中学３年生・高校１年生)

A
2018-ふうせん-解説
- 考案国：アイルランド
- 正解
  - 「1と3」
- 説明
  - AとC，DとBは同じに見えます。CをAに、DをBに、それぞれ置き換えて見比べてみましょう。
- 実際のコンピュータでは
  - 文字の並びを比較することはコンピュータの処理でよく行われます。私たちが使う文字の検索でも、「Aとaのような大文字と小文字」「あとアのような仮名」を同一に扱う検索は便利に使われています。
2018-水もれ-解説
- 考案国：南アフリカ共和国
- 正解
  - 「4」
- 説明
  - 最初は、16軒の家のどこで水漏れがおきているか分かりません。
  - まず、15 個の中で真ん中の8軒目と9軒目のバルブを閉めます。メーターが動いてると1軒目〜8軒目のどこかで、メーターが止まると9軒目から16軒目のどこかで、水漏れがおきていることが分かります。つまり、水漏れがおきている可能性がある場所が16ヶ所から8ヶ所と、半分になります。
  - 水漏れがおきている可能性がある場所の真ん中のバルフを閉めることで水漏れがおきている可能性がある場所を半分にするということを繰り返すと、2回目で可能性がある場所は4ヶ所となり、3回目で2ヶ所ととなり、4回目で1ヶ所、つまり、水漏れしている場所を特定できます。
- 実際のコンピュータでは
  - 上の説明のように、目的のデータや障害の箇所を探すのに、対象を半分ずつに分けて探しているデータや原因がどちらにあるかを探していく方法を、二分探索といいます。
  - この問題では、原因を左から順に探していくと、最悪の場合は16回の検査が必要になってしまいます。4回で原因を特定できる二分探索のようなアルゴリズムは大量のデータを扱うときに有用です。
2018-スケジュール-解説
- 考案国：インドネシア
- 正解
- 説明
  - コンピュータになったつもりで、ルールのとおりに色を塗っていきましょう。
- 実際のコンピュータでは
  - コンピュータは「文字の入力」「日本語変換」「ネットワーク通信」「時刻の表示」などの複数の処理を、細かく処理を分割することで並行して行っています。ひとつの処理だけに時間を使って他の処理が止まらないように、全体の処理のバランスを取ることは重要です。
B
2018-矢印-解説
- 考案国：ハンガリー
- 正解
- 説明
  - 条件を満たす解を見つけるため、ある矢印から始めて、仮に白か黒に決め、その矢印が指している矢印の色を条件を満たすように仮に決める（複数の可能性がある場合は、そのうちの一つを選び）ということを繰り返し、うまく選べなくなったら複数の可能性から選択した矢印まで戻り、まだ試してない可能性を選択するという方法があります。戻ったとき、もう選ぶ選択肢がない場合は、さらに戻ります。
  - このように、ある状況から可能性を探索し、ステップバイステップで進み、行き詰まるともとに戻る方法を、情報科学ではバックトラックと言います。バックトラックは、8クイーンパズルや数独などのパズルを解くのに、また，ナップザック問題などの組み合わせ最適化問題を解決するのにも使用できます。他にも、様々な応用があります。
    https://ja.wikipedia.org/wiki/バックトラッキング
     https://ja.wikipedia.org/wiki/論理プログラミング
　

2018-関係-解説
- 考案国：カナダ
- 正解
  - 「5」
- 説明
  - まず、上段中央の「=4」の円に注目します。この円とつながっている円はちょうど4つなので、つながっている4つの円全てに色を塗りましょう。
  - 次に、右下の「=2」の円に注目します。この円とつながっている円はちょうど2つなので、つながっている2つの円に色を塗りましょう。
  - すると下の図のようになります。この図で、残りの円の条件を見ていくと、すべての条件が満たされていることがわかります。よって、この時点で塗られた5個の円が正解になります。
- 実際のコンピュータでは
  - いろいろな組み合わせが考えられる問題を、手当たり次第に解くと時間がかかってしまいます。この問題には9個の円がありましたので、すべての組み合わせを考えると512通りについて考えなければなりません。そこで、今回の解法のように、調べる組み合わせの候補を少なくする工夫が行われています。
2018-手旗信号-解説
- 考案国：台湾
- 正解
  - 「QPPTP」
- 説明
  - 「水平を0、垂直を1」で表すと、次のようになります。
    問題　：１００１００１０
    RPQSR：１００１００１１０
    RPSP ：１００００１０
    QPPTP：１００１００１０
    TSQ　：１００１００１1
- 実際のコンピュータでは
  - コンピュータは2進数で動くため、文字も０と１の組み合わせで表現しています。どの文字にどのような０と１の組み合わせを割り当てるかは重要です。この問題のように「S（１０）はQ（１）とP（０）の並びとも解釈できる」ような割り当てにすると、解釈に曖昧さが生まれてしまいます。実は、選択肢にはありませんが、TSP (１００１００１1) も問題の図の信号になります。
2018-行と列-解説
- 考案国：ベルギー
- 正解
- 説明
  - 考えやすくするために、円に文字を振りましょう。そうすると、上の3個は同じ横一列にありますので、「AとB」「BとC」「AとC」が線でつながります。下の「DとE」「EとF」「DとF」も同じです。そして、縦に「AとD」「BとE」「CとF」がつながります。このような形です。
  - 選択肢にはこのような形はありませんが、選択肢の中から「3個がそれぞれつながっている」形が2組あり、それらが3本の線でつながっている形を探すと、次のものが正解になります。
- 実際のコンピュータでは
  - コンピュータでは、解きたい問題を点と線で表す「グラフ」と呼ばれるデータ構造を使うことがあります。グラフでは、この問題のように、「どの点とどの点が線でつながっているか」は重要ですが、その配置は意味を持ちません。
C
2018-短いプログラム-解説
- 考案国：イギリス
- 正解例
- 説明
  - 解答を得るアプローチを1つ示しましょう：
    - まずは、ブロックの数が多くても良いのでゴールに到達できる単純なプログラムを作成します。
    - 次に、同じブロックのパターンを繰り返している部分を repeat でまとめて、使用するブロックの数を減らします。これを何度か繰り返します。
  - 道順によっては、使用するブロックの数を十分小さくできないこともあるでしょう。この迷路の場合は、スタートのあたりは道順がいろいろと考えられますが、図１のように、途中からは一本道です。途中からの道順を良く観察して解析すると、図２のようにパターンを繰り返せば良いことが分かるでしょう。
  - 図２の道順で進むことにして、単純なプログラムをつくって見ましょう。図３・図4のようにまとめられそうなブロックのパターンを見つけます。
    図1 図2
    図3 図4
- 実際のコンピュータでは
  - この問題では、繰り返されているパターンを見つけて、問題を解決しました。
    これは、プログラマのコードをタイプする手間を節約するだけでなく、エラーがあった場合にそれをすばやく修正するのにも役立ちます。
    繰り返しを活用しなければ、この問題では29個のブロックを使用する必要があります。
  - 情報科学やプログラミングにおいて、パターンにうまく抽出することは、あるタイプの問題に対する適切な解決方法を知る上で重要です。パターンや類似の特性に気づくことで、解決法の道筋を見つけ、問題を解決できます。
  - この問題であなたが発見した繰り返しのパターンは、アルゴリズムやプログラムの反復構造になります。
2018-デバッグ-解説
- 考案国：イラン
- 正解
  - 「3番目のステップを、6番目の位置（終了直前）に移動する」
- 説明
  - 登録が完了する前にユーザが作られてしまうと、中途半端なユーザができてしまいますし、同じユーザ名で再度作ることもできなくなってしまいます。そこで、すべての登録作業が正しく行われた後でユーザを作ることが必要です。
- 実際のコンピュータでは
  - プログラムのミスを発見して修正することを「デバッグ」といいます。デバッグは、プログラム開発の重要な作業のひとつです。この問題では、「必要な処理がすべて成功したら登録する」「完了しない処理がひとつでもあれば登録しない」というトランザクションの考え方を扱っています。
2018-検査-解説
- 考案国：チェコ
- 正解
  - 「容器は振られることはない」
- 説明
  - プログラムを、1行ずつ指さしながら1行目から動かしてみましょう。まず、1行目でAに0が入ります。次に2行目でAに1が足されます。次に3行目から6行目に処理が移りAに1が足されます。次に7行目から2行目に戻り、Aに１が足されます。
    このように、何度も何度もAに1が足されていきますが、8行目が処理されることはありませんので、容器が振られることはありません。
- 実際のコンピュータでは
  - 1940年代に作られた、アセンブリ言語と呼ばれるプログラミング言語では、行に番号が付けられて、次の処理をどの行に移すのかを "go to" の形で記述していました。このようなプログラミング言語で、プログラムを書くことは難しくありませんが、処理を追って動作を確認することは難しく、大きなプログラムを書くのには適していません。現在では "go to" を使わない、構造化された言語が良く使われています。
2018-ダンスフロア-解説
- 考案国：アメリカ
- 正解例
- 説明
  - ルールの上部にある3個のタイルの白と黒の組み合わせは 2*2*2 = 8通りです。それぞれに対して、下部のタイルを白か黒にするので、ルールとなる組み合わせは全部で 2*2*2*2*2*2*2*2 = 256通りあります。その中の16通りが、オーナーの希望を叶えるルールとなります。
  - 上の正解例は「XOR」の考え方を利用しています。上部の真ん中のタイルを無視して両端のタイルだけに着目し、「上段の両端のタイルが同じ色なら、下段のタイルは白」「上段の両端のタイルが違う色なら、下段のタイルは黒」と考えると、正解のルールになります。
  - 例えば、次の図も16通りある正解の１つです。
  - 残りの正解はどのようなルールか考えてみましょう。
- 実際のコンピュータでは
  - この問題では、Conwayが考案したセル・オートマトンを扱っています。いくつかの単純なルールから、複雑なドット絵のパターンを扱えるライフゲームを作ることができます。