SeniorAnswer2016

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

A
2016-ダンスの練習-解説
- 考案国: スロバキア
- 正解
- 説明
  - ダンスにそのときの状態を加えてみます．
  - すると、Bの絵が4と5のポーズと合っていることがわかります．
    1.両膝（りょうひざ）を曲げる
    2.両手を上げる: 両膝を曲げて、両手は上
    3.頭をかたむける: 両膝を曲げて、両手は上で、頭は傾いている
    4.両膝（りょうひざ）を伸ばす: 両膝を伸ばして、両手は上で、頭は傾いている
    5.頭を逆にかたむける: 両膝を伸ばして、両手は上で、頭は逆に傾いている
    6.両手を下ろす: 両膝を伸ばして、両手を下ろして、頭は逆に傾いている
    7.頭をまっすぐに戻す: 両膝を伸ばして、両手を下ろして、頭はまっすぐ
2016-魔法の薬-解説
- 考案国: 日本
- 正解
  - 「D」
- 説明
  - 実験1で，A, B, C の3つのコップは耳/歯/鼻の3箇所に影響しました．よって，A, B, C はすべて薬であり，水ではないことがわかります．
  - 実験2で，A, D, E の3つのコップは耳/目の2箇所に影響しました．よって，この中のひとつは水です．実験1でAが水でないことがわかっていますので，水は D か E のどちらかです．
  - 実験3で，C, D, F の3つのコップはひげ/鼻の2箇所に影響しました．よって，この中のひとつは水です，実験2で D, E のどちらかが水であることがわかっていますので，水はDであることがわかります．
- 解説
  - この問題では，いくつかの事実が与えられ，それらの事実から未知の事実を推定します．
  - これは論理的な推論 (logical reasoning) によって実現されます．
    論理は情報科学において，重要な役割を担っています．
  - コンピュータが扱うデータの最小単位ビットは，1 (真/Ture) か 0 (偽/false) のいずれかの値を持ちます．
    コンピュータ内で扱う全ての情報は，ビットの組み合わせで表せれます．
    コンピュータは，どのような判断に従うのか判定するのに論理を用いますが，それは，真 (1) か偽 (0) のビットで表されます．
  - この問題は，集合にも関連しています．
    集合と論理は密接に関連しています．
2016-L字ゲーム-解説
- 考案国: 台湾
- 正解
  - 「ビ太郎が必ず勝つ」
- 説明
  - ビ太郎が最初に中央に置いた後，ビバ助が置ける場所は3箇所です．
  - その次は，どの場合でもビ太郎は置くことができますが，その後にビバ助が置ける場所はありません．
- 解説
  - 対戦ゲームの可能な局面の遷移は，上の説明のような図／グラフ (graph) で表すことができます．
  - 説明のゲーム木 (game tree) では，根／ルート (root) は初期局面を表し，可能な指し手ごとに次の局面を表す頂点／ノードに矢印が出ます．
    ゲーム木は，有向グラフ (directed graph) の特別な場合になっています．
  - ゲーム木は，どのような手を打てば良いのか探索するのに利用されます．
  - ゲームの性質によって，根／ルートからの距離（レベル）ごとに探索してく幅優先探索 (breadth-first search, BFS) が有効なこともあれば，進めるだけ進んで戻る (backtracking) 深さ優先探索 (depth-first search, DFS) が有効なこともあります．
    この２種類の探索法は，必要とするメモリ量など異なる特徴をもっています．
2016-コルクのおもちゃ-解説
- 考案国: 日本
- 正解
- 説明
  - 上の左から2番目のコルク（図の赤丸）は，左右の両方のおもちゃの部品になってしまっています．
- 解説
  - この問いの「作品」では，同じパターン（コルクの栓をつなげたおもちゃ）が繰り返されます．
  - この問題の目的は，選択肢にある「作品」が，使用可能なパターン（コルクの栓をつなげたおもちゃ）で合成/構成できるかどうかはを判定することです．
  - 使用可能な部品を用いて何かを合成/構成すること，適切に構成できるかどうかを確認することは，情報科学の様々な場面で見られます．
    プログラミングにおける構文解析なども，このような例と言えるでしょう．
B
2016-パーティの横断幕-解説
- 考案国: チェコ
- 正解
  - 「32」
- 説明
  - 切り取られた部分を考えます．
  - 紙の色は、「YRRB」が繰り返されるという規則に従っています．
  - 切り取られた部分は「YRRB」で終っています．
  - 「・・・」の部分の長さは分かりませんが，切り取られた部分の長さは，4nで表されます．nは0以上の整数です．
  - 31, 32, 33, 34 の中で，4n で表現できるのは 32 だけです．
- 解説
  - 情報の中にパターンを見つけるのは，様々な問題で重要です．
    例えば，DNA 配列中の遺伝子は塩基の並び方のパターンによって表さます．
    そのため，ある条件を満たす繰り返しは部分列を検出することは生命情報学では基本的で重要な問題です．
  - このような問題に関連して文字列中に特定の文字列やパターンが現れるかを判定するのに，文字列処理アルゴリズムやパターンマッチングアルゴリズムが用いられます．
- 注
  - 問題文中の『ビ太郎の妹は，この紙の一部を下図のようにある場所で切り取りました．切り取った紙の「・・・」の部分の長さは分かりません．』は，チャレンジ終了後の2016年12月3日に表現を変更しました．
2016-セグウェイ-解説
- 考案国: チェコ
- 正解
  - 「下の壁」
- 説明
  - 右ボタンが押された回数は10回で，左ボタンが押された回数は8回です．
  - 結果として，右に2回多く回っているため，乗り物は最初の上向きから見て逆方向の下を向いているはずです．
- 解説
  - この問題で扱われている乗り物は，２つのモータで車輪を回転することで走らせることができます．自動車と比べてその場で左右に回転できることが特徴です．
  - この問題の図は，「左右のモータを制御するプログラム」と，「そのときどきの乗り物の状態」の両方を示しています．
2016-読取機-解説
- 考案国: マレーシア
- 正解
- 説明
  - 2台の読取機は「上の行の右端と、下の行の左端が同じ色」のときに異なる動作をします．
  - 2台の読取機が同じ動作になる画像はすべての行で「上の行の右端と、下の行の左端が違う色」になっているはずです．
- 解説
  - FAXやスキャナのように紙から画像を生成する装置や，デジタルカメラのように写真を撮影する装置は，実際の画像を縦横の細かいマス目（画素またはピクセル）に分解してデジタルのデータを作ります．
  - この問題では，同じ色が連続して現れる画像を「白白白白」を「白4」のような短いデータで表現する圧縮技法を扱っています．
2016-KIXバーコード-解説
- 考案国: オランダ
- 正解
  - 「BC16」
- 説明
  - KIXコードは表を見て，記号を文字に変換することで読み取れます．
  - この問題の正解は，表の赤い丸の部分からわかります．
- 解説
  - Kix コードは，バーコードの一種で，オランダの郵便で使われています．
  - バーコードは，機械可読な符号（コード）で，郵便の自動仕分けなどにも使われています．
  - この問題の符号化方法は，バーコードの上部と下部を分割し，それらを利用して表を構成します．このような技法や情報を表現する際によく使われる手法の一つです．
C
2016-再帰的な絵-解説
- 考案国: オーストリア
- 正解
- 説明
  - 左の指示書を見ると，「左側に半分の円を描くこと」「右側に互いに逆向きに1の指示書を入れること」が読み取れます．
  - 指示書の右側の部分に1を入れることを考えると，上下の真ん中で半分の円が接することがわかります．
  - 選択肢をよく見ると，「半円同士が接している」ものはこれだけです．
- 解説
  - この問題のように自己（と「ある意味で」同じもの）を参照する指示・操作を再帰といいます．再帰は情報科学において重要な概念です．
  - 再帰的な解法はしばしば他の解法より簡潔に記述できるものの，理解するのが少しばかり困難なこともあります．
  - 再帰における停止条件は，処理が無限に繰り返さるのを避ける重要な役割があります．
  - 再帰的なパターンは自然界でもよく見られます．
2016-黒く塗れ-解説
- 考案国: 日本
- 正解
  - 「3（箇所）」
- 説明
  - 例をよく見ると，「同じ色の組合せは黒に、違う色は白になる」ことがわかります．
  - 問題では，同じ色の場所は「上の中央」と「右の中央」「右の下」の3枚です．
- 解説
  - ブール関数は，基本的な計算モデルの一つです．
  - 白いマス目を 0 あるいは偽 (FALSE) と解釈し，黒いマス目を 1 あるいは真 (TRUE) と解釈すると，この操作は下図のようになります:
2016-MapReduce-解説
- 考案国: カナダ
- 正解
  - 「8」
- 説明
  - 式は内側の括弧から順に計算できます．
    (+ (max (min 3 9 2) (· (max 0 4) (min 0 4))) (min (max 3 6) (max 5 7 2)))
    (+ (max 2 (· 4 0 )) (min 6 7 ))
    (+ (max 2 0 ) 6 )
    (+ 2 6 )
    8
- 解説
  - この問題は，関数型言語や入れ子構造を題材としています．
  - 入れ子の考え方は，スプレッドシートなどでも一般的に使われています:
    （例えば，列ごとに値の総和を求めるなどの）ある関数を用いてデータを生成し，
    （例えば，最大を求めるなどの）別の関数を用いて別のデータを生成する．
    この計算モデルは，様々な方法が利用されています：
    このような言語には Lisp, Scheme, Racket などがありますし，
    C# のラムダ式や Python の filter のように，より現代的な言語でも利用されています．
  - 理論的な話をすると，この問題で扱っている計算の表現方法は，非演算子（オペランド）の前に演算子（オペレータ）を記述するポーランド記法の特別な場合になっています．
2016-赤と青のボール-解説
- 考案国: イタリア
- 正解
  - 「ゲームが終わらないのは、『一番下が青』である4通りの並びです」
- 説明
  - 次のように，一番下（左から3番目）が青（B）のときは，ボタンを押していくうちに「RBRRBR」になります．
    BBB→RBRB→RBRRB→RBRRBR
    BRB→RBRB→RBRRB→RBRRBR
    RBB→RBRR→BRB→RBRB→RBRRB→RBRRBR
    RRB→RBRR→BRB→RBRB→RBRRB→RBRRBR
  - 「RBRRBR」というパターンは、ボタンを押していくうちに「RBRRBR」に戻りいつまでも終わりになりません．
    RBRRBR→BRBRR→BBRB→RBRBB→RBRRBR
- 解説
  - このパズルは，Emil Leon Post により提案された文字列の書き換えを用いた計算モデル "Post production system" を題材にしています．
    Post は 1920 年代に草案したものの，公表されたのは 1943 年です．
    Emil Leon Post (1897-1954) はポーランド生まれのアメリカ人で，計算可能性理論の草創期に活躍した数学者であり論理学者です．
  - 書き換え系 (rewriting system) は，式や文字列などのある部分を別のものに置き換えるシステム（系）です．
    書き換えモデルは，オブジェクト（操作対象）とそれに対する適用可能な操作や変形を定義する関係の有限集合からなるシステム（系）と見なすことができます．
  - 文脈自由文法 (CFG) などの形式文法も書き換え系の一種です．
    例えば，乗法と加法の系はわずかの規則からなる文脈自由文法で定義できます．