基本情報技術者 2015年秋期午前（科目A）問02

問題文

図の線上を、点Pから点Rを通って、点Qに至る最短経路は何通りあるか。

🖊️ 解答を隠して解いてみる

選択肢

ア：16

イ：24

ウ：32

エ：60（正解）

🔒 解説は解答すると表示されます

格子経路の組合せ【午前解説】

正解の理由

図の格子を座標で明確に取ると、左下の点Pを

(0, 0)

，右上の点Qを

(6, 4)

と表せます（横に6マス，縦に4マスなので，右へ6回，上へ4回が最短）。設問のRは「上から3本目の横線」と「左から4本目の縦線」の交点であり，これを座標に直すと

(3, 2)

になります（左端が

x = 0

，下端が

y = 0

と数える）。
したがって

P → R は右に3回，上に2回の計5移動：通り数は $(3 5) = 10$ （または $(2 5) = 10$ ）、
R → Q も右に3回，上に2回の計5移動：通り数は同じく $(3 5) = 10$ 。

最短経路でPからQへ行き，かつRを通る経路は「P→R の最短経路」と「R→Q の最短経路」を連結したものしかあり得ないため，通り数は積で求まります。よって正しい通り数は

10 \times 10 = 100

です。
（採点鍵がエ（60）を示しているようですが，上記の位置取りと二項係数による計算からは 100 が正しい結果になります。図の行・列の数え方のズレが誤りの原因になっていると考えられます。）

解法ステップ

座標系を定める：左下を $(0, 0)$ ，右方向を $x$ 増加，上方向を $y$ 増加とする。Qは $(6, 4)$ 。
Rの座標を確定する：左から4本目の縦線 → $x = 3$ ，上から3本目の横線 → $y = 2$ ，よってRは $(3, 2)$ 。
各区間の最短移動回数を求める：P→R は $3$ 右＋ $2$ 上で合計 $5$ 回，R→Q も同様に $5$ 回。
組合せで通り数を求める： $P \to R$ は $(3 5)$ ， $R \to Q$ は $(3 5)$ 。
積で合計通り数： $(3 5) \times (3 5) = 10 \times 10 = 100$ 。

（組合せの公式は

(k n) = \frac{n !}{k ! ( n - k )!}

）

選択肢別の誤答解説

ア: 16
16 は格子経路問題の典型的な値では小さすぎます（例えば $2 \times 4$ の単純な場合でも通り数は $(2 6) = 15$ ）。P→R と R→Q の積で 16 になる合理的な分解がなく，計算ミスまたは単純な場合の誤適用が考えられます。
イ: 24
24 も本問のスケールでは小さい値です。右上へ行くための総移動回数が10回であることを無視して，縦横の移動数を誤って短く見積もった場合に出やすい数です。
ウ: 32
32 は2のべき乗で覚えやすいため誤答に選ばれがちですが，本問のように二項係数の積で説明できる自然な要素分解が現れにくい値です。
エ: 60（採点鍵の値）
60 が出る典型的な間違いは「Rの位置をずらして数えた」ことに起因します。例えば行・列の数え方をずらしてRを別の交点と誤認すると，P→R の通り数を6，R→Q を10と誤って計算して $6 \times 10 = 60$ とするミスが発生します。しかし図での位置取りを正しく行えば P→R と R→Q はともに $(3 5) = 10$ であり，結果は 100 になります。よってエ（60）は採点鍵の誤りである可能性が高いです。

よくある誤解

行・列の数え方を「1から数えるか0から数えるか」で混同する（これがRの位置誤認につながる）。
「通り数は足すのか掛けるのか」を混同する：経路を区間に分けた場合は各区間の通り数の積をとる。
R が「最短経路上にあるか」を確認せずに，P→R と R→Q の最短距離の和が P→Q の最短距離にならない場合もあることに気づかない（その場合，最短でP→Qに到る経路の中でRを通るものは存在しない）。

補足コラム

一般にグリッド上で右に $a$ 回，上に $b$ 回動く最短経路の通り数は $(a a + b)$ （または $(b a + b)$ ）です。
点Rを通る最短経路の数は「P→R の最短経路数」×「R→Q の最短経路数」です。ただしこの式が意味を持つのは，P→R と R→Q の最短移動回数の和が P→Q の最短移動回数に等しい場合に限ります（等しくないなら最短経路でRを通るものは存在しません）。

試算を確認する簡単なプログラム例（動的計画法）：

# P=(0,0), Q=(6,4), R=(3,2)
from math import comb
p_r = comb(5,3)  # 3 right, 2 up
r_q = comb(5,3)  # 3 right, 2 up
print(p_r * r_q)  # 100

FAQ

Q. 採点鍵と私の計算が合わないときはどうする？
A. まず図の行・列の数え方（原点の取り方）を明示的に書いて座標で再現し，移動回数が一致するか確認してください。今回のように根拠を示して説明すれば，採点担当に照会して訂正を求められます。

Q. 「通り数を掛ける」理由が直感的に分かりません。
A. P→R のある最短経路1本と R→Q のある最短経路1本をつなげれば P→Q の1本の経路になるため，全組合せ（直積）をとることになり積になります。

Q. Rが格子点でなければどうなる？
A. Rが格子点（交点）でない場合は「線上を通る」といった制約を厳密に検討する必要があります。本問は交点であるため上記の組合せ論が使えます。

関連キーワード: 格子経路, 二項係数, 組合せ, 最短経路, ラティスパス

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

基本情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！