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

格子上の最短経路（点P→R→Q）【午前2 解説】

要点まとめ

• 結論：P→R は $3$ 右・$2$ 上、R→Q も $3$ 右・$2$ 上で、それぞれの最短経路数は $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$ より合計 $10\times 10=100$ 通りです。
• 根拠：格子上の最短経路は右（R）と上（U）の順序だけの組合せ問題になり、長さが固定された順列の組合せ数で求まります。
• 差がつくポイント：R の位置（格子上の座標）を正確にとらえること。R が P と Q を結ぶ任意の最短経路上にあるときは、候補数は P→R と R→Q の積になります。

正解の理由

• P = $(0,0)$
• R = $(3,2)$ （左から4本目＝$x=3$、上から3本目＝$y=2$）
• Q = $(6,4)$

• P→R は右 $3$、上 $2$ の順列数：$\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$
• R→Q は右 $3$、上 $2$ の順列数：$\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$

よくある誤解

• R の位置を間違えて数える（「上から何本目」「左から何本目」の解釈ミス）。1 本目の数え方で座標がずれると組合せが大きく変わります。
• P→R と R→Q を別々に数えず、P→Q 全体の組合せから R を含むものを引くという面倒な方法にしてミスする。分割して積をとる方が簡単です。
• 「最短経路」の定義を勘違いして、右・上以外の動きを許してしまい（往復など）余分に数えてしまう。

解法ステップ

1. 格子の横・縦のマス数と線の本数を確認し、座標系を決める。ここでは左下を $(0,0)$ とする。
2. P, R, Q の座標差を求める：P→R は右 $3$, 上 $2$、R→Q は右 $3$, 上 $2$。
3. 「右」と「上」の並べ方の数を組合せで数える。長さ $n$ のうち上が $k$ 回出る並べ方は $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$。
   • P→R：$\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$
   • R→Q：$\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$
4. 中継点 R を通る最短経路は P→R と R→Q の組合せの直積なので $10\times 10=100$。

選択肢別の誤答解説

• ア: 16 — 明らかに小さすぎます。P→R や R→Q の個別数の最小値が既に 6 や 10 程度になるため、積が 16 になる組合せはありえません。
• イ: 24 — P→R と R→Q のどちらかを $4$ や $6$ と誤認して掛け合わせたときに出やすい数ですが、各区間の正しい組合せ数と一致しません。
• ウ: 32 — 同様に、片方の区間数を過小評価すると出る値です。具体的誤りは「R の位置をずらして dx,dy を小さく見積もる」ことで生じます。
• エ: 60 — よくある誤りの結果として出る値です（例えば P→R を 10 通り、R→Q を 6 通りと誤って計算して $10\times 6=60$ とするなど）。しかし本問の正しい P→R, R→Q は共に $10$ 通りで、正答は $100$ です。

補足コラム

• 格子経路の基本テクニック：点 A$(0,0)$ から B$(m,n)$ への最短経路数は $\left(\genfrac{}{}{0ex}{}{m+n}{n}\right)$（または $\left(\genfrac{}{}{0ex}{}{m+n}{m}\right)$）です。中継点を通る問題では各区間の組合せ数を掛け合わせます。
• 実務的視点：経路数は「自由度」（右や上を選ぶ回数）に依存します。テストではまず「何回右へ何回上へ」を正確に見積もる癖をつけましょう。

FAQ