Pythonで島での生存が可能かどうかを判定するアルゴリズム

問題の概要

ある島に店が1軒だけあり、この店は日曜日を除いて毎日営業しているとします。この状況で、以下の3つの値が入力として与えられます。

• N:1日に購入できる食料の最大数
• S:生き延びる必要がある日数
• M:1日に必要な食料の数

今日が月曜日であり、これからのS日間を生き延びなければならないとします。このとき、そもそも生存が可能かどうかを判定し、可能な場合は食料を買いに行くべき最小の日数を求めるのがこの問題の目的です。

具体例

たとえば、S = 12、N = 24、M = 3 という入力が与えられた場合を考えてみましょう。

この場合の出力は (True, 2) となります。つまり生存は可能で、食料の購入はわずか2日で足りるということです。24単位の食料があれば8日間(今週の月曜日から翌週の月曜日まで)を乗り切ることができ、その後さらに12単位を購入すれば、残りの4日間を賄えるためです。

解法のアプローチ

この問題を解くには、以下の手順に従います。

1. 生存不可能なケースを先に除外する
   「N × 6 < M × 7 かつ S > 6」または「M > N」のいずれかに該当する場合は False を返します。
   これは、日曜日に店が閉まっているため、1週間(7日間)を乗り切るには少なくとも6日分の購入で7日分の食料を確保できる必要があるからです。また、1日の最大購入量Nが1日の必要量Mを下回る場合も、当然ながら生存できません。
2. 必要な購入日数を計算する
   count =(M × S)÷ N の商(整数部分)とし、M × S が N で割り切れない場合は count に1を加えます(要するに切り上げ計算です)。
3. 結果を返す
   True と count を返します。

実装例

それでは、実際のPythonコードを見てみましょう。

def solve(S, N, M):
    if ((N * 6) < (M * 7) and S > 6) or M > N:
        return False
    else:
        count = (M * S) // N
        if ((M * S) % N) != 0:
            count += 1
        return (True, count)

S = 12
N = 24
M = 3
print(solve(S, N, M))

入力

12, 24, 3

出力

(True, 2)

まとめ

このアルゴリズムのポイントは、日曜日の店休日を考慮して「6日間の購入で7日分を賄えるか」という条件で生存可否を判定することです。判定後は、総必要食料量(M × S)を1日の最大購入量(N)で割り、切り上げるだけで最小購入日数が求まります。計算量はO(1)と非常に効率的で、面接や競技プログラミングでもよく見られる典型的な数学的思考の問題といえます。