Pythonでn人の列における自分の位置候補数を求めるプログラム(前方最低a人・後方最大b人の条件)

3つの整数 n、a、b が与えられたとします。n 人の人々が一列に並んでおり、その中に自分も含まれています。しかし、自分が何番目にいるのかは分かりません。分かっているのは、前方には少なくとも a 人、そして後方には最大で b 人の人がいるということだけです。この条件を満たす自分の位置として考えられるパターンが何通りあるかを求めるのが問題です。

入力例と出力例

たとえば n = 10、a = 3、b = 4 が入力された場合、出力は 5 になります。これは、列全体が10人で、前方に少なくとも3人、後方に最大4人がいる状況です。このとき、自分の位置は先頭を0番目として 0、1、2、3、4 のいずれかになり得ます。たとえば位置0なら前方に9人・後方に0人、位置4なら前方に5人・後方に4人となり、どちらも条件を満たします。

解法のアプローチ

この問題は、次のシンプルな条件分岐で解くことができます。

• a + b < n の場合:b + 1 を返します。

• a + b >= n の場合:n - a を返します。

なぜこれで正しいのか

位置を先頭を0番目として数えると、前方に少なくとも a 人必要なため、自分の位置は a 番目以降(a, a+1, …, n−1)でなければなりません。一方、後方にいる人数は最大でも b 人なので、位置は n−1−b 番目以降でもある必要があります。つまり答えは「min(n − a, b + 1)」で表され、上記の条件分岐はこの式をそのまま場合分けしたものになっています。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

def solve(n, a, b):
   if a + b < n:
      return b + 1
   if a + b >= n:
      return n - a

n = 10
a = 3
b = 4
print(solve(n, a, b))

入力

10, 3, 4

出力

5

このように、条件を整理して最小値・最大値の範囲を考えることで、O(1) の計算量で答えを導き出せます。競技プログラミングでも頻出のパターンなので、ぜひ覚えておきましょう。