情報の勉強高校 情報Ⅰ

共通テスト 過去問の解説

2025年 追・再試験 第2問B 問1

迷路の壁をビットで表す2つの方法と、必要なデータ量(空欄ク〜シ)

まず問題を開く

問題の全体は、大学入試センターの公式サイトで見られます(2025年(令和7年度)追・再試験「情報Ⅰ」、問題冊子 18〜19ページ)。問題を横に開いて読みながら、この解説を使ってください。

問題のPDFを開く ↗公式の問題ページ ↗公式の正解 ↗

答え

空欄正解中身
ク2Yの左端から2ビット目(上の壁)
ケ②右のマスの、左端から1ビット目が1
コ④4N²
サ②2N²+4N
シ2N>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なら右へ動ける)。

上左右下このマスは 11001100左上右下壁がある=1、壁がない=0左→上→右→下 の順に並べる
4ビットの並び順(左・上・右・下)を最初に確かめる。

② 2つのマスの間の壁は1本なのに、2回書かれている(ク)

Xのマスのすぐ下にYのマスがあります。Xの左端から4ビット目は「Xの下の壁」です。それは、Yから見れば「Yの上の壁」と同じ1本の壁です。上はYの左端から2ビット目なので、クは 2。

Sさんの方法では、となり合うマスの間の壁がどれも2回ずつ記録されます。これがTさんの言う「重複していて無駄」です。

XY← 同じ1本の壁X の4ビット左上右下4ビット目Y の4ビット左上右下2ビット目
上下に並ぶマスでは「上のマスの下」=「下のマスの上」。

③ Tさんの表し方:左と上だけの2ビット(ケ)

Tさんは、各マスの左と上の壁だけを2ビットで表しました。右と下の壁は、それぞれ右どなりのマスの左、下どなりのマスの上として記録されているので、重複がなくなります。一番右の列の右の壁、一番下の行の下の壁を書くために、右と下に1列ずつ仮想的なマスを足します。

右に動けるかを調べるには、自分のマスではなく右のマスの1ビット目(左)を見ます。それが1なら右に壁があります。ケは ②。③の2ビット目は右のマスの「上」の壁なので関係ありません。

キャラクターのいるマス右のマスこの壁は1本だけ右のマスの2ビット左上1ビット目これが 1 なら右に壁がある→ ケ は ②
重複をなくす代わりに、隣のマスを見に行く手間が増える。

④ 迷路全体のデータ量を式にする(コ・サ)

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さん(2ビットずつ)222222222222222Sさん(4ビットずつ)444444444N²+N+N=15マス2N²+4N=30ビットN²=9マス4N²=36ビットオレンジのマス=右と下にくっつけた仮想的なマス(角はいらない)
N=3 で数えて、式が合っているか確かめる。

⑤ 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 を計算して確かめます。

よくある間違い

確かめの1問(このサイトの問題)

8×8 マスのボードゲームの盤を、Sさんと同じように「1マスにつき4ビット」(上下左右の壁の有無)で表します。盤全体を表すのに何バイト必要ですか。ただし 1 バイト=8 ビットとします。

関係する単元

同じ大問のほかの設問

問題の著作権は大学入試センターにあります。このページでは、解説に必要な部分だけを引用しています。解説・図・確かめの問題はこのサイトで作ったものです。