JuniorAnswer2019
ジュニア問題解説(中学3年生・高校1年生)
- A
2019-買い物するビ太郎-解説
- 考案国:日本
- 正解
- 「6番目に高い」
- 説明
- ビ太郎が持っているお金で払える額を高い順に並べると次のようになり、「11010」は6番目に高いことがわかります。
1番: ฿11111
2番: ฿11110
3番: ฿11101
4番: ฿11100
5番: ฿11011
6番: ฿11010
7番: ฿11001
…
- ビ太郎が持っているお金で払える額を高い順に並べると次のようになり、「11010」は6番目に高いことがわかります。
- 実際のコンピュータでは
- この問題では、ビ太郎は1種類のお金を1個ずつしか持っていないので、金額を「その種類のお金を持っているか、いないか」という1か0で表すことができました。
- これはコンピュータが計算で使う2進数と似ています。2進数では0と1だけを使って数を表現します。この例の5桁の2進数では32通りの数を表現できます。
2019-二重駐車-解説
- 考案国:ドイツ
- 正解
- 「Iの車」
- 説明
- Iの車を出すためには、Nの車を動かす必要があります。そのためには、左と右のどちらの方向にもOとMの車があるため、最初にOかMの車を動かしてから、次にNの車を動かす必要があります。
- 実際のコンピュータでは
- この問題を考えるときに、コンピュータはすべての車について、可能性をひとつひとつ調べていくかもしれません。このような「しらみつぶし」の調べ方はブルートフォース(総当り検索)と呼ばれます。
- 車の効率のよい駐車方法は多くの研究が行われています。駐車中の車を自動的に最適な場所に移動させるシステムも研究されています。
2019-キープ-解説
- 考案国:日本
- 正解
- 「3本」
- 説明
- 1本のキープでは、0,1,2,3の4通りを表せます。2本のキープでは、4通り×4通りで16通りを表せます。3本のキープでは、4通り×4通り×4通りで64通りを表せますので、50種類を表すことができます。
- 実際のコンピュータでは
- 私たちは生活の中で、「1つの桁で10通りの数を表す」10進法で数を扱っています。これは「結び目が0個から9個あるキープ」に相当します。10進法では、1本のキープで0から9までの10通りの数を表し、2本のキープで10通り×10通りで0から99までの100通りの数を表します。
- コンピュータは「1つの桁で2通りの数を表す」2進法で数を扱っています。これは「結び目が0個か1個のキープ」に相当します。
2019-梱包マシン-解説
- 考案国:日本
- 正解
- 「ブロックL」
- 説明
- 梱包マシンは次のように動きます。
1.「3, 1, 1」のボタンで、下から「L, C, D」の順にブロックが置かれます。
2.「4, 4」のボタンで「D, C」が順に取り除かれ、「L」が残ります。
3.「2, 3」のボタンで「I, O」の順にブロックが置かれ、下から「L, I, O」になります。
4.「4」のボタンで「O」が取り除かれ、下から「L, I」になります。このとき、上から2番目のブロックは「L」です。
- 梱包マシンは次のように動きます。
- 実際のコンピュータでは
- この機械では、最後に置かれたブロックが最初に取り除かれます。このようなデータ構造をスタックと呼びます。
- スタックはコンピュータのプログラムでよく使われます。たとえば「1+(2*(3+4)+5)」のような文字列の中で開き括弧「(」と閉じ括弧「)」の数が同じかどうかを確かめるときに利用されます。
- B
2019-ボトルリサイクル-解説
- 考案国:ルーマニア
- 正解
- 説明
- 正解は2です。
選択肢ごとに図を描いてみるとわかりやすいです。図で、白色はwhite、緑色はcolorです。
図1
図2
図3
図4
- 正解は2です。
- 白色のボトルを生産するには、次の3種類の入力が考えられます。
A color color color B color color color C color color white D color white white 正解の2
- 実際のコンピュータでは
- コンピュータのCPUは論理回路と呼ばれる微小な電子回路から作られています。論理回路ではNOT, OR, AND, XORなどが使われます。この問題ではAND, OR, NOTを使いました。説明図では実際の電子回路と同じ図で表しています。
- 実際の論理回路では、電気信号の有無で1と0を表します。これは論理回路の真と偽を表しています。この問題では白色(white)を真(1)、緑色(color)を偽(0)の役割で考えました。
- ANDでは両方の入力が真のときに出力が真になります。
- ORでは少なくともどちらかの入力が真のときに出力が真になります。
- NOTでは入力と出力が逆になります。入力が真のときは出力が偽になり、入力が偽のときは出力が真になります。
- ANDでは両方の入力が真のときに出力が真になります。
2019-スカーフ制作機-解説
- 考案国:リトアニア
- 正解
- 説明
- 正解はAです。
図の上の中央にある草は続けて現れることができますが、図の下の中央にある木の枝は繰り返すことができないことに注意しましょう。また、図の出口の青い花から、入口の紫の花に戻ることはできません。
- 正解はAです。
- 実際のコンピュータでは
- この問題のように、入口から矢印をたどりながら「今どこにいて、次はどこに移る」を繰り返して出口に行けるかを表す図をオートマトンまたは状態遷移図と呼びます。
- オートマトンは、プログラムが文法通りに書かれていることを確認したり、PCやスマートフォンで入力された文字を日本語に変換する処理、電卓で数式が正しいことを確認する処理などで利用されています。
- たとえば、多くの電卓では「12+3=」を入力すると正しく計算が行われますが、「12++3=」はエラーになって計算されません。これは電卓の中に「数字の繰り返しと、演算記号と、数字の繰り返しと、最後に=」を表すオートマトンが定義されているため、正しい数式かどうかをチェックできているのです。
2019-トンネル-解説
- 考案国:タイ
- 正解
- 「BBGBGG」または「BBBGGG」
- 説明
- 出口でいちばん左が青(B)になるためには、入口の左がBBであることが必要です。そうでないと出口でいちばん左が緑(G)になってしまいます。
出口でいちばん右が緑(G)になるためには、入口の右がGGであることが必要です。そうでないと出口でいちばん右が青(B)になってしまいます。
そうすると、入力の真ん中の2つはBGかGBになります。どちらの場合も出力の真ん中の2つはBGになるため、両方とも正解であることがわかります。
- 出口でいちばん左が青(B)になるためには、入口の左がBBであることが必要です。そうでないと出口でいちばん左が緑(G)になってしまいます。
- 実際のコンピュータでは
- インターネットの通信で、パケットと呼ばれるデータはIP通信のルールで相手に送られます。ネットワークは「学校内のネットワーク」のように他のネットワークと分かれていて、お互いに直接通信できません。そこでルーターと呼ばれる中継装置を置くことで、適切な経路でパケットを送るようにしています。
2019-倉庫-解説
- 考案国:ロシア
- 正解
- 「10」
- 説明
- 1, 2, 3, 4, 5番のハリネズミと31, 32, 33, 34, 35番のハリネズミは荷物を移動しなくてすみます。
まず、問題の例にあるように、1番のハリネズミは荷物を移動しなくてすみます。実は1番だけでなく、2番から5番のハリネズミも同じです。
次に倉庫の数(5個と6個)を考えると、5で割っても6で割っても余りが0になる数は、0の次は最小公倍数の30です。
そこで、「0に続く1, 2, 3, 4, 5」の次は、「30に続く31, 32, 33, 34, 35」であることがわかります。
- 1, 2, 3, 4, 5番のハリネズミと31, 32, 33, 34, 35番のハリネズミは荷物を移動しなくてすみます。
- 実際のコンピュータでは
- この問題では、データを分割して格納する考え方を扱いました。ハッシュ法と呼ばれるアルゴリズムでは、データを複数の入れ物(倉庫)に分割して格納し、取り出すときは値からどの入れ物に入っているかを計算で求めることで、高速にデータを取り出します。
- わかりやすい例だと、生徒の名簿をアルファベットごとの入れ物に分けておき、「MattiaさんはMの入れ物に入れる」ようなイメージです。
- 今回の問題では、どの入れ物に入っているかを、剰余(割り算の余り)で求めました。例えば倉庫が5個のとき、「1番の倉庫は、1や6のように5で割ったときの余りが1の荷物を入れる」「2番の倉庫は、2や7のように5で割ったときの余りが2の荷物を入れる」「5番の倉庫は、5や10のように5で割ったときの余りが0の荷物を入れる」というやり方です。このようにすると、「13番の荷物はどこにあるかな?」と考えたときに、「13を5で割った余りは3だから3番の倉庫!」とすぐにわかります。
- C
2019-3つの数字で描け-解説
- 考案国:スロバキア
- 正解
- 説明
- 実際に、紙に描いてみるとわかりやすいと思います。「1, 4, 1」の場合はこのようになります。
- 実際に、紙に描いてみるとわかりやすいと思います。「1, 4, 1」の場合はこのようになります。
- 実際のコンピュータでは
- コンピュータは与えられたプログラムで動きます。プログラムの命令はひとつひとつが意味を持っていて、コンピュータはそれを順番どおりに実行します。
- この問題では、コンピュータになったつもりで、与えられた命令を実行しました。命令を読んで、ひとつひとつがどのような結果になるかを考えることは、プログラムを作るときと、プログラムを修正するときに重要なスキルです。
2019-席順-解説
- 考案国:カナダ
- 正解
- 説明
- 条件1から、DはAの向かい側に座ります。AとDの場所が決まりました。
条件5から、EはDの隣に座ります。左右のどちらでも構いません。Eの場所が決まりました。
条件2から、HはEとGの間に座ります。HとGの場所が決まりました。
条件3から、FはAとDの隣ではありません。Fの場所が決まりました。
条件4から、GとCの間には1人が座ります。Cの場所が決まりました。
最後に、空いている場所にBが座ります。これで全員の場所が決まりました。
- 条件1から、DはAの向かい側に座ります。AとDの場所が決まりました。
- 実際のコンピュータでは
- 論理では、規則に従うことと、順序と否定を理解することが重要です。この問題では、「~でない」を意味する否定が重要な役割を果たしていました。たとえば「FはAとDの隣にいない」は「FはAの隣にいないし、FはDの隣にいない」と言うこともできます。
- 論理的な考え方に興味のある生徒は、ドモルガンの法則に興味を持つかもしれません。これは「(AまたはB)ではない」は「(Aでない)かつ(Bでない)」と同じ意味になるという法則です。たとえばある生徒が「(放送部または自転車通学)でない」ということは「(放送部でない)かつ(自転車通学でない)」と同じ意味ということです。
- このように、論理的な表現を記述したり、書き直したり、組み合わせたり、簡潔にしたりするスキルは、コンピュータ科学の世界でとても役に立ちます。
2019-観察-解説
- 考案国:ドイツ
- 正解
- 「BACED」または「EACBD」
- 説明
- 2種類の正解が考えられます。0秒から10秒の間に、誰かが市庁舎のドアを開けるか閉めました。10秒から20秒の間に、TomとTinaが出会いました。彼らは少し離れて立っています。20秒から30秒の間に、TomとTinaは腕を組んで歩きました。並んでいるのでひとつの四角に見えます。30秒から40秒の間に、誰かが市庁舎のドアを開けるか閉めました。40秒から50秒の間に、たくさんの木の葉が散っています。
- 実際のコンピュータでは
- 画像を自動処理することは、空港や駅のような公共の場所で安全を確保するために重要です。権利のない人が侵入したことを確認したり、犯罪の容疑者を特定することが可能です。ただし、プライバシーの問題があるので、継続的に撮影することは注意が必要です。
- この問題では、荒い画像を撮影できる安価なカメラを使って、どのような情報を得られるかを扱いました。実際の画像処理では、スーパーやコンビニのレジでバーコードを読むような簡単な処理から、お客さんの写真からどのような年齢層や性別の人が買物をしているかを判別するような高度な処理までの、さまざまな画像処理が実用化されています。
2019-秘宝の地図-解説
- 考案国:ベトナム
- 正解
- 説明
- 地図には7個の区域があります。そこで、宝を含めて丸(●)が6個しかないものは正解ではありません。
- 次に、それぞれの区域が何個の区域と隣り合っているかを数えます。宝のある区域は5個の区域と隣り合っています。そこで、宝から4本しか線が出ていないものは正解ではありません。
- 残りの2つのどちらが正解かを調べるために、区域にaからgまでの名前を付けて、それらが何個の区域と隣り合っているかを数えてみましょう。
区域aは、b, eの2個と隣接しています。
区域bは、a, c, d, e, gの5個と隣接しています。
区域cは、b, dの2個と隣接しています。
区域dは、b, c, gの3個と隣接しています。
区域eは、a, b, f, gの4個と隣接しています。
区域fは、e, gの2個と隣接しています。
区域gは、b, d, e, fの4個と隣接しています。
隣接している数を見ると、「5個が1区域、4個が2区域、3個が1区域、2個が3区域」あることがわかります。 - 正解でないほうの選択肢を描くと、このようになりました。3個の区域が3個ありますので、正解でないことがわかります。
- もうひとつの選択肢を描くとこのようになりました。「5個が1区域、4個が2区域、3個が1区域、2個が3区域」あることがわかります。
念のために、図に区域を書き込んで確かめることができます。
- 実際のコンピュータでは
- この問題では、点(頂点)と線(辺)で表される「グラフ構造」が実際の問題を解くときに有効なことを学びました。頂点は区域を表し、辺は「区域が隣り合っている」という関係を表しています。
- グラフ構造は、複数のものごとの関係を表すときに便利です。数学者とコンピュータ科学者は、グラフ構造を使うことで、現実の問題を解決するためのたくさんの有用なアルゴリズムを考えてきました。