共通テスト 過去問の解説
2025年 追・再試験 第2問B 問1
迷路の壁をビットで表す2つの方法と、必要なデータ量(空欄ク〜シ)
まず問題を開く
問題の全体は、大学入試センターの公式サイトで見られます(2025年(令和7年度)追・再試験「情報Ⅰ」、問題冊子 18〜19ページ)。問題を横に開いて読みながら、この解説を使ってください。
答え
| 空欄 | 正解 | 中身 |
|---|---|---|
| ク | 2 | Yの左端から2ビット目(上の壁) |
| ケ | ② | 右のマスの、左端から1ビット目が1 |
| コ | ④ | 4N² |
| サ | ② | 2N²+4N |
| シ | 2 | N>2 |
この問は合わせて 10 点(ク・ケ・コ・サ・シ 各2点)。 正解は大学入試センターの公表した正解と照合済み。
場面の整理
第2問Bは、SさんとTさんが迷路のゲームを作る話です(問1・問2)。迷路はマス目を壁(太線)で区切ったもので、キャラクターは上下左右の操作を受けると、その向きに壁がなければとなりのマスへ動きます。2人は、迷路をコンピュータの中でどう表すか(データの表現)と、コンピュータが動かすキャラクターをどう財宝へ向かわせるか(アルゴリズム)を考えていきます。
問1では、2人がそれぞれ考えた迷路の表し方を比べます。Sさんは、1マスごとに上下左右の壁の有無を4ビットで表しました。Tさんは、1つの壁が2つのマスで重複して記録されるのは無駄だと考え、1マスごとに左と上の壁だけを2ビットで表しました(右と下に1列ずつ仮想的なマスを足します)。クは重複している壁のビットの位置、ケはTさんの方法で右の壁を調べる方法、コ・サはN×Nマスの迷路全体に必要なビット数、シはTさんの方法の方がデータ量が少なくなる条件です。
図2(Sさんの方法)と図3(Tさんの方法)は、迷路の一部を数で表したものです。図そのものは公式の問題PDFで見てください。図2では、Xと書かれたマスのすぐ下に、Yと書かれたマスがあります。
ケ・コ・サの解答群(引用)
ケ の解答群 ⓪ キャラクターのいるマスの,二つのビットの両方が1 ① キャラクターのいるマスの,二つのビットのどちらかが1 ② キャラクターのいるマスの右のマスの,左端から1ビット目が1 ③ キャラクターのいるマスの右のマスの,左端から2ビット目が1 コ・サ の解答群 ⓪ 2N ① 2N² ② 2N²+4N ③ 4N ④ 4N² ⑤ 4N²+2N ⑥ 32N² ⑦ 32N²+64N
出典:大学入試センター 令和7年度 大学入学共通テスト 追・再試験『情報Ⅰ』第2問 B 問1 のケ・コ・サの解答群(図1〜図3は省略。公式の問題PDFで見てください)
考え方
① Sさんの表し方:1マス=4ビット
Sさんは、1つのマスの4つの辺について、左→上→右→下の順に「壁があれば1、なければ0」を並べ、4ビットの2進数で表しました。例えば 1100 は、左と上に壁があり、右と下には壁がないマスです。
この表し方だと、キャラクターのいるマスの数を見るだけで、どの向きに動けるかがすぐ分かります(3ビット目が0なら右へ動ける)。
② 2つのマスの間の壁は1本なのに、2回書かれている(ク)
Xのマスのすぐ下にYのマスがあります。Xの左端から4ビット目は「Xの下の壁」です。それは、Yから見れば「Yの上の壁」と同じ1本の壁です。上はYの左端から2ビット目なので、クは 2。
Sさんの方法では、となり合うマスの間の壁がどれも2回ずつ記録されます。これがTさんの言う「重複していて無駄」です。
③ Tさんの表し方:左と上だけの2ビット(ケ)
Tさんは、各マスの左と上の壁だけを2ビットで表しました。右と下の壁は、それぞれ右どなりのマスの左、下どなりのマスの上として記録されているので、重複がなくなります。一番右の列の右の壁、一番下の行の下の壁を書くために、右と下に1列ずつ仮想的なマスを足します。
右に動けるかを調べるには、自分のマスではなく右のマスの1ビット目(左)を見ます。それが1なら右に壁があります。ケは ②。③の2ビット目は右のマスの「上」の壁なので関係ありません。
④ 迷路全体のデータ量を式にする(コ・サ)
N×N マスの迷路を考えます。
- Sさん:N² 個のマスに4ビットずつなので 4N² ビット。コは ④。
- Tさん:元の N² マスに、右に足した列の N マスと、下に足した行の N マスを加えた N²+2N マスに、2ビットずつ。2(N²+2N)=2N²+4N ビット。サは ②。右下の角のマスは、左の壁も上の壁も迷路の外なので、なくてよいのです。
N=3 で確かめると、Sさんは 36 ビット、Tさんは 15マス×2=30 ビットです。
⑤ Tさんの方が少なくなるのは N>2 のとき(シ)
2N²+4N < 4N² となる N を求めます。両辺から 2N² を引くと 4N < 2N²、N は正なので両辺を 2N で割って 2 < N。シは 2 です。
N=2 のときはどちらも 16 ビットで同じ、N=1 のときは Tさんの方が多くなります。迷路が大きくなるほど、Tさんの方法の得が大きくなります。下のプログラムで N=1〜6 を計算して確かめます。
よくある間違い
- クで 4 と答える:Xの4ビット目(下)と同じ壁は、Yの「下」ではなく「上」です。Yから見た向きで考えます。
- ケで③を選ぶ:右のマスの2ビット目は、右のマスの「上」の壁です。キャラクターの右にある壁は、右のマスから見ると「左」です。
- サで ① 2N² を選ぶ:右と下に足した仮想的なマス(N+N 個)の分を忘れています。
- シで「Tさんの方がいつも少ない」と考える:N=1 では Tさんの方が多く、N=2 では同じです。式で確かめましょう。
確かめの1問(このサイトの問題)
関係する単元
同じ大問のほかの設問
問題の著作権は大学入試センターにあります。このページでは、解説に必要な部分だけを引用しています。解説・図・確かめの問題はこのサイトで作ったものです。