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

問題文

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

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

選択肢

ア：16

イ：24

ウ：32

エ：60（正解）

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

格子上の最短経路の通り数【午前解説】

正解の理由

図を格子座標に落とし込むと、点Pから点Rへは右に2マス、上に3マスの移動が最短（順序は任意）であり、点Rから点Qへは右に5マス、上に1マスの移動が最短です。
したがってP→Rの最短経路数は

(2 5) = 10

、R→Qの最短経路数は

(1 6) = 6

となり、P→R→Qの全体の最短経路数はこれらの積で

10 \times 6 = 60

です。よって正解はエの60通りです。

（座標の取り方の一例：Pを原点

(0, 0)

、長方形の格子交点を整数座標で表すと、Rが

(2, 3)

、Qが右上隅の交点

(7, 4)

に対応するため、Δx,Δyが上記になります。）

解法ステップ

図を格子（格子点＝交点）として座標化する。単位を格子1マスとする。Pは左下外側で原点 $(0, 0)$ とするとわかりやすい。
図からRとQの座標を読み取る（Rが右に2、上に3の位置、Qが右上隅＝Rより右に5、上に1の位置）。
「右にa回・上にb回」の順序を並べ替える問題とみなし、通り数は $(a a + b)$ または $(b a + b)$ で求める。
- P→R： $a = 2, b = 3$ より $(2 5) = 10$
- R→Q： $a = 5, b = 1$ より $(1 6) = 6$
中継点Rを経由する全体の最短経路数は、それぞれの最短経路数の積（独立に順序を決められるため）： $10 \times 6 = 60$ 。

選択肢別の誤答解説

ア: 16
おそらく「P→Rを4手（例えば右2・上2）と誤認」して $(2 4) = 6$ 等の誤計算や、R→Qを単純に別の小さな組合せと掛け合わせた結果かもしれません。実際のΔはP→Rが合計5手であり、16は得られません。
イ: 24
24は $(2 4) \times (1 6) = 6 \times 6 = 36$ でもなく、 $(2 5) \times (1 4) = 10 \times 4 = 40$ でもないため、いずれかの区間の増減（特にR→QのΔxを誤って少なく見積もる）による誤りです。正しいR→Qは6手です。
ウ: 32
32は二つの区間の通り数を誤って2進的に扱ったり（例えば $2^{5} = 32$ のような誤解）、P→Rの通り数を8と見積もった場合に生じ得ますが、図のステップ数に基づく組合せ計算からは導けません。
エ: 60（正解）
P→Rが $(2 5) = 10$ 、R→Qが $(1 6) = 6$ で積が60と一貫して導けます。

よくある誤解

格子の「線（交点）」と「マス（セル）」の数を混同する：交点の数は列数＋1、行数＋1になるため、移動ステップの数（Δx,Δy）がずれることがあります。
P・Qが外側にある点の扱いでのオフバイワン：Pが枠の「すぐ外」にあるとき、枠の角までの1歩を忘れる／余分に数える間違いが起こりやすいです。
「最短経路」の定義を見落とす：右上方向のみの最短経路を前提にする（右／上以外の動きを許すと手数が増え、最短とはならない）。

補足コラム

一般に格子上で右に $a$ 回、上に $b$ 回動く最短経路の数は $(a a + b)$ （または $(b a + b)$ ）で与えられます。中継点を経由する場合は区間ごとに独立に数え、その積を取れば良い（最短条件が各区間で満たされる場合）。
動的計画法（パスカルの三角形）を使うと、格子上の全交点について経路数を累積的に計算できます。終点の通り数が求めやすく、プログラム実装にも向きます。

簡単な計算例（Python）

import math
def C(n,k): return math.comb(n,k)
paths_PR = C(5,2)   # 10
paths_RQ = C(6,1)   # 6
paths_total = paths_PR * paths_RQ  # 60
paths_total

FAQ

Q. なぜP→Rが右2・上3と分かるのですか？
A. 図中の格子を単位長さで数えると、Pから枠の左下角を1右で入ったうえで、Rの位置はその角からさらに右2・上3分離れているため、P→Rの最短移動は右2・上3の組合せになります。座標を明示してΔx,Δyを確認することが重要です。

Q. 中継点が複数ある場合の扱いは？
A. 各中継区間それぞれで最短となる移動回数（Δx,Δy）を求め、それぞれの通り数を掛け合わせます（区間ごとに順序は独立なので積になる）。

Q. 動ける方向に制約がなければどうなる？
A. 右・上のみでなく往復が許されるなら最短経路の概念が変わり、組合せで簡単に求められなくなるため「最短経路」の条件を明確にしてから計算します。

関連キーワード: 格子経路、組合せ、ΔxΔy、パスカウント、動的計画法

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

\ せっかくなら /

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

クイズ画面へ遷移する→

すぐに利用可能！