慶應義塾大学環境情報学部　2018年情報入試問題解説

キミのミライ発見大学入試問題研究プロジェクト

監修・執筆　間辺広樹先生(神奈川県立柏陽高等学校教諭)

日本で唯一の本格的な情報での入試選抜を実施しているのは、慶應義塾大学(総合政策学部・環境情報学部)です。18年度の問題と、解説・学習方法をまとめました。

「キミのミライ発見」サイトでは、14年からの参考試験も併せて解説も掲載しています。併せて、入試状況、その選抜で重要な小論文対策に関しての情報も示しました。

<本ページ下に案内してあります>

入試学習対策にも、情報・小論文の学習や指導にも、ご活用いただけましたら幸いです。

※慶応義塾大学の湘南藤沢キャンパス（SFC）にある環境情報学部と総合政策学部では、2018年度入試において３度目となる「情報入試」が実施されました。本稿では、環境情報学部に出題された問題について解説します。

まず問題を見てみよう!

→18年度環境情報学部

→総合政策学部の入試問題解説はこちら

→「情報」入試に向けた学習法はこれだ!

全体

情報-1は、情報化社会におけるセキュリティや法に関わる問題であった。新しい用語とその意味を知っているかを問われるため、毎年政府が出している「消費者白書」などに目を通しておく必要があった。

情報-2は、２進数表現に関する問題であった。教科書レベルの基本的な問題から、2次方程式の解と桁落ち誤差を組み合わせた発展的な問題となっていた。その際、数学I・数学IIで学習した「解の公式」「解と係数の関係」「分母の有理化」を適用することが求められた。

情報-3は、アルゴリズムの問題であった。扱っている題材はチェスのナイトの動きを扱った古典的なものであるが、初めてこの問題を目にした受験生が、すぐに解法を思いつくような簡単なものではなかった。そのため、この問題を完答できた受験生は、解き方を知っていたか、あるいは、その場でひらめきを得ることができたかのどちらかではないか、と考えられる。

情報-4は、ライントレースカーの制御方法に関する問題であった。与えられたルールから、ロボットカーの動きを想像する力が問われた。

情報-5は、文字列を操作して別の文字列へと変化させる編集距離に関するプログラムの問題である。情報-3と同様に、古典的なアルゴリズムを題材とした問題ではあるが、高等学校レベルを超えた難問であった。

以下、大問ごとに解くためのポイントを解説する。

情報-1

(ア) ウィルス対策のためには、バックアップに使用する装置・媒体は、常時パソコンと接続しておくと被害を拡大させる恐れがあるため、必ずしも接続しておく必要はない。したがって、(1)が誤り。

(イ) 生体認証の問題。正解は(5)。

(ウ) 事実の伝達にすぎない報道は、著作権による保護の対象にはならないが、新聞を作る過程で配置などに個性が現れているものには著作権が生じる。したがって、正解は(3)。

(エ) 著名人のパブリシティ権の侵害についての問題。正解は(1)。

(オ) 他人のプライバシーを侵害した場合、被害者に財産的な損害が生じていなくても、精神的な損害を与えていれば賠償責任を負う場合がある。したがって、正解は(1)。

(カ) プロバイダ責任制限法に関する問題。正解は(4)。

(キ) 個人や組織などが保有する遊休資産の貸し出し提供サービスをシェアリングエコノミーという。それが行われる多くのプラットフォームでは取引終了後にお互いを評価し合う仕組みになっている。したがって、正解は(6)。

(ク) サーチエンジンなどの学習機能によって、ユーザが好む方向へと情報が偏る現象をフィルターバブルという。したがって、正解は(4)。

情報-2

２進数表現に関する問題である。教科書レベルの基本的な問題から、2次方程式の解と桁落ち誤差を組み合わせた発展的な問題となっている。その際、数学I・数学IIで学習した「解の公式」「解と係数の関係」「分母の有理化」を適用することが求められている。

(ア) は教科書レベルの問題で、位取り記数法や２の補数表現の原理がわかっていれば解ける問題である。「2の7乗は128」であるから、表現方法に関わらず128種類の数を表現できる。

７ビットで０と正の整数だけを表現する方法では、0から始めているのでその最大値1111111(2) = 127(10)である。２の補数表現を用いると、最小値－064、最大値063までの整数が表現できる。

(イ) １０進法表現と２進法表現の変換に関する問題である。１０進法表現の数を２のベキ乗の和で表すことが考え方の基本であるが、小数においてもその原理は同じである。

1.125₁₀ = 1・1 + 0・(1/2) + 0・(1/4) + 1・(1/8)

　　　 = 1・2⁰ + 0・2 ^-1+ 0・2 ^-2 + 1・2 ^-3

となるため、係数を並べた1.001₂が1.125₁₀の２進法表現となる。

また、1.6₁₀を2進数法表現に変換する問題も同様だが、計算が少し面倒になるので、以下の方法を習得すると、計算が楽になる。

(1) まず小数部分の0.6に着目する。

(2) 次のように、「小数部分のみを2倍する」という計算を繰り返す。

　　0.6 → 1.2 → 0.4 → 0.8 → 1.6 → 1.2 → 0.4 →（循環する）

(3) このとき出てくる整数部分を並べたもの0.100110・・が、0.61₁₀の２進法表現である。従って、求める値は1.6₁₀ = 1.100110・・₂という循環小数となる（解答は下線部分）。

(ウ) 2次方程式の「解の公式」がそのまま答えになるので、選択肢より該当する２つを選ぶ。

（数学Iで「2a分のマイナスbプラスマイナスルート・・」と覚えたに違いない）

その上で、この問題は「桁落ち誤差」を扱っている。桁落ち誤差とは、値がほぼ等しい数同士の減算を行った場合に、有効数字が落ちてしまう誤差をいう。

情報-3

問題文を読み、決められたルールの中で課題解決ができるかを問うアルゴリズムの問題である。格子状のマスに複数の駒が配置されていて、チェスのナイトの動き（下図）をさせながら、状態を変化させている。実際に駒を動かして確かめることはできないので、状態を紙に書いたり、想像しながら考えることになる。また、この問題を解決するためのアルゴリズムはそう簡単に見つかるものではないため、受験生はかなりの苦戦を強いられたのではないだろうか。

（ア）では、駒の動き方を確認している。3×3のマスの左上に駒があるとき、1手目と２手目で移動できるマスを考えさせている。元に戻ることを許さないとすると、移動できるマスは下図の通り（６と８，３と７）である。

（イ）では、黒と白それぞれ２つずつの駒を配置し、黒と白を入れ替えるための最低回数を求めさせている。

この問題は、単純に考えただけでは動かしたい箇所に別の駒があるため、移動させることができない。そこで、発想の転換が必要となる。ここでは、一定の方向に回転させながら、状態の変化を観察してみる。動かす順番はいろいろと考えられるが、次のように、

初期状態→ 状態1 → 状態2 → 状態3 → 最終状態

と変化させていくことで、入れ替えが実現する。これは、中央以外の箇所に４つの駒を入れていくという作業の繰り返しである。

それぞれの状態の変化には4回ずつの駒の移動があるため、合計の移動回数は16回となる。この解答は、「空いている箇所に駒を埋めていく」ことと、「どちかか（この場合は右）に回転させていく」ことで問題点を整理し、課題解決につなげている。

ただし、この方法では最短であることの保証がない。そこで、“グラフ”を用いて考えてみる。

＜別解＞

グラフとは、頂点と辺だけでそれらの繋がりを表現したものである。この問題では、下の左図のようにマスに番号を付けると、それぞれの駒が移動できる場所は限られているため、まとめると右図の時計のような数同士の繋がりができる。これが、この問題のグラフ表現の一例である。

ここで黒と白とを入れ替えるのは、この盤を右（または左）に４つ動かせばよいことと、それが最短の方法であることがわかる。１つのコマに4回の操作が必要であることから、答えは４×４＝１６回である。

（ウ）は難問である。（イ）の別解として紹介したように、グラフに置き換えて考えることで解決へと繋がるが、そのアイデアはすぐに思いつくようなものではない（詳しくは、オライリー・ジャパンの名著「アルゴリズムパズル」などを参照されたい）。ここでは、下図にて最短となる駒の移動手順例のみを紹介するに止める。合計の移動回数は、16回である。

情報-4

車両型ロボットがライントレースすることを想定し、光センサの位置やしきい値、ロボットの振る舞いなどを考える問題である。問題文に書かれた2つのルールから、問題前半のロボットは真っ直ぐに走ることはできず、常にセンサの入力値に応じて右へ左へと蛇行を繰り返しながら進んでいくロボットであると想像する必要がある。

（解答）

＜センサ位置＞

センサの位置は選択肢(1)のAが適切。

＜ロボットの初期位置＞

２つのルールから、ラインを外れたら左の車輪が前転するようになっていると読み取れることから、センサとラインとの位置関係は、選択肢(1)のラインの左際に配置することが望ましい。

＜分岐のあるコースのゴール地点＞

そのため、ラインに分岐があったとしても左へ左へと進むことから、問題の図の上を走った結果は左端である選択肢(1)のAとなる。

＜しきい値＞

ロボットの動作を決定するしきい値は、ライン外とライン上とで分ける必要があることから、選択肢の中でその中間にあるのは選択肢(3)の100だけである。

＜センサを増やした場合のルール＞

問題の後半は、センサが左右２つとなり、８の字型のコースを進むためのルール作りが問われている。問題文にあるルールを動作を想像しながら整理すると、

・ルール１は、両方のセンサーがライン外に出てしまったコースアウト状態であるから、両輪を後転させてコースに戻す必要がある。従って、選択肢(2)両輪とも後転が正解。

・ルール２は、左のセンサが外に出ている状態であるから、左輪を前転にする必要がある。従って、選択肢(4) 左輪は前転、右輪を後転が正解。

・ルール３は、ルール２の逆であるから、選択肢(3) 右輪は前転、左輪を後転が正解。

・ルール４は、両方のセンサーがライン上にある状態であるから、そのまま前進させる必要がある。従って、選択肢(1)両輪とも前転が正解。

情報-5

ある文字列に対して1文字単位の挿入・削除・置換を繰り返して、別の文字列へと一致させる編集距離（レーベンシュタイン距離）に関するプログラムの問題である。文字列の類似性を測る古典的なアルゴリズムではあるが、高等学校の情報科が扱うレベルをはるかに超えていて、初めてこのアルゴリズムに触れる受験生にとっては、超難問であったのではないか。特に、「空文字を文字列と認識すること」、「文字列を１文字ずつに分解して比較すること」、「２変数を用いて処理を行うこと」、「帰納的に計算式を定義すること」、「文字列A,Bの編集距離をd(A, B)と書くこと」など、高校生にとってはそれぞれに「難解な概念」である。これらを組み合わせて問題解決するには、相当なプログラミング的素養が求められる。

ただし、問題文中には次のような例示やヒントが書かれているので、これらを利用しながら一つでも多くの答えを導くことが必要である。

●「かながわ」→「かがわ」（削除）

●「さいたま」→「あいたま」（置換）→「あいちま」（置換）→「あいち」（削除）

（１）では、「何回か操作した後」の末尾の操作手順から、編集距離を求める方法を理解することを求めている。具体的には、文字列A, Bの末尾が一致するかどうかで場合分けして考える。

例えば、例として「かながわ」と「かがわ」が提示されているが、この４文字と３文字とを比較しなくても、末尾が「わ」で一致しているため、それを除いた「かなが」と「かが」の３文字と２文字を比較すればよい。

これがd(A, B) = d(A’, B’)という(64)の解となる。

末尾が異なっている場合については、「さいたま」と「あいち」の例からわかる。

最終的な編集距離は３であるが、これは、A = “さいたま” の末尾１文字を取り除いた A’ = “さいた” を B = ”あいち” まで変化させた編集距離であるd(A’, B)に１を加算したものである。したがって、d(A, B) = d(A’, B) + 1が (68)の解となる。

操作手順は、一通りではない。

1.「あいち」→「あいちま」（挿入）→「さいちま」（置換）→「さいたま」（置換）

2.「あいち」→「さいち」（置換）→「さいた」（置換）→「さいたま」（挿入）

と逆に辿ってもいい。操作に無駄がなければ編集距離は一致する。

最後の操作が置換である場合の(66)と、挿入である場合の(67)についても同様に、以下のようになる。具体例で考えるとわかりやすい。

(66) d(A, B) = d(A’, B’) + 1

(67) d(A, B) = d(A, B’) + 1

（２）では、（１）の考え方を拡張する。文字列A, Bをそれぞれ１文字ずつ分解した上で、空文字からはじめて末尾まで逐次的に文字の比較を繰り返し、編集距離を算出する手順を理解することが求められる。また、そのアルゴリズムを実装したプロブラムに適切に穴埋めをして、正しく動くプログラムへと完成させる問題となっている。

例として、A = “さいたま”, B = “あいち” で考えよう。分解すると次のようになり、問題文からそれぞれの文字数は4と３である。

編集の過程はさまざまであるが、すべての部分文字列の編集距離を一覧にすると次のような表となる。

例えば、※は部分文字列の「あ」と「さいたま」の編集距離４を表している（手順には無駄がある）。

「次の処理を考える」とき、その手前までの処理との関係を考える必要があるが、それは表中２×２の４セルにおける「右下セルと他の３つのセルの関係」を考えることである。例えば、太枠の右下部分（△）には、部分文字列「さいた」と「あい」との編集距離が入るが、この場合は、「さい」と「あい」編集結果（上の部分）を踏まえて「た」を挿入するという処理をすることが、最も効率が良い。

もちろん、状況によって（左上）や（左）から処理を行う必要がある。その際、置換、削除、挿入を行うには１を加算する必要があるが、その時点での末尾が一致していれば、（１）でも問われたように加算の必要はない。

このように、m文字とn文字からなる２つの文字列を、それぞれ１文字ずつに分け、その文字数に空文字分を加えた(m+1)×(n+1)回の比較を繰り返すことで、編集距離を計算することができる。

では、問題を見てみよう。まずは、プログラムに使われている変数が、それぞれ何を表すかを見極めるとよい。

・最終的な出力はXm,nであるから、これが編集距離である。

・問題文からA, Bの文字数がそれぞれm, nであり、選択肢(20), (21)から反復に用いるカウンタ変数がそれぞれi, j である。

・文字列はそれぞれAiやBjのように１文字ずつに分解して比較に使うが、「前の文字までの処理」を前提として次の処理を行うため、初期状態として空文字A0とB0及び、編集距離X0( = 0 )を用意しておく。

次に１行目〜６行目の初期設定を見る。

１行目でjの値を0にしているので、２行目の処理は、jをカウンタ変数としたループである。したがって、(66)(67)には、選択肢(21)のj<=nが入る。

３行目からの処理Aでは、変数X0,jとして文字列A（さいたま）の空文字に対する、文字列B（あいち）の各文字の編集距離を設定する。そのため、

(71)(72)には、選択肢(14)のjが入る。

7行目以降がメインの処理となる。７行目ではiの初期値(73)(74)を1とし、8行目からの処理で、iをカウンタ変数としたループを行う。したがって、(75)(76)には、選択肢(20)のi<=mが入る。

8行目から図中矢印のように進む２重ループが始まる。外側が文字列A（さいたま）を分割したAiごとの処理であり、内側でAiとBj（j=1,2,3）とを比較して計算する部分文字列ごとのXi,jの計算を行なっている。

10行目で文字列B（あいち）の空文字に対する、文字列A（さいたま）の各文字の編集距離を設定する。そのため、(77)(78)には、選択肢(13)のiが入る。

11行目で変数jの初期値(79)(80)を1とし、12行目からの処理で、jをカウンタ変数としたループを行う。したがって、(81)(82)には、選択肢(21)のj<=nが入る。

13行目で、そこまでの処理に対応した、部分文字列毎の末尾に応じた分岐を行う。従って、(83)(84)には文字を比較する選択肢(22)のAi = Bj が入る。

14行目からが、このプログラムの核心とも言える編集距離の加算処理を行なっているが、これ以降は（１）の結果と同じものを選択肢より選べばよい。すなわち、末尾が同じ場合の(85)(86)には、加算をしない選択肢(23)のXi,jを入れ、末尾が異なる場合の(87)(88)〜(91)(92)には選択肢(28), (29), (30)を入れ、その最小値（選択肢(31)）をXi,jとすることで、最終的な編集距離Xm,nを得る。