Pythonで全コースを履修するのに必要な最小学期数を求めるプログラム

問題の概要

n 個のコースがあり、それぞれ 1 から n までの番号が付けられているとします。また、relations という配列が与えられ、relations[i] はペア (prevCourse_i, nextCourse_i) を含んでいます。これは「コース prevCourse_i を先に履修しなければ、コース nextCourse_i を履修できない」という前提関係を表します。さらに、最後のパラメータとして k が与えられます。

1 学期あたり最大 k コースまで履修できますが、そのためには履修したいコースの前提科目を、前の学期までにすべて修了しておく必要があります。このとき、すべてのコースを履修し終えるまでに必要な最小の学期数を求めるのが目的です。

具体例

たとえば、入力が次のような場合を考えてみましょう。

この場合の出力は 3 になります。理由は以下の通りです。

• 第1学期： コース 1 と 2 を履修する。これによりコース 3・4・5 を受講できるようになる。
• 第2学期： コース 5 と、3 または 4 のどちらか一方を履修する。
• 第3学期： 残りのコースを履修して全課程を修了する。

したがって、合計 3 学期が必要となります。

解法のアプローチ

この問題はトポロジカルソートの考え方と貪欲法（グリーディ法）を組み合わせて解きます。各学期において、履修可能なコースの中から「多くの後続科目を持つコース」を優先的に選ぶことで、全体の学期数を最小化します。

具体的には、次の手順で処理を進めます。

• taken := すでに履修済みのコースを管理する新しい集合
• g1 := n 個の空リストを持つリスト（各コースの前提科目を格納）
• g2 := サイズ n の新しいリスト（各コースが前提となっている科目を格納）
• w := サイズ n のリストで、0 で初期化（各コースの重み）
• semester := 0（学期数のカウンタ）
• relations 内の各要素 x に対して：
  • g1[x[1]-1] の末尾に x[0]-1 を追加
  • g2[x[0]-1] の末尾に x[1]-1 を追加
• weight := g1 の各要素の長さからなる新しいリスト
• i を 0 から n-1 まで繰り返す：
  • g1[i] 内の各要素 x に対して：w[x] := w[x] と weight[i] の最大値
• taken のサイズが n 未満である間、以下を繰り返す：
  • courses := 新しい空リスト
  • i を 0 から n-1 まで繰り返す：g1[i] が空で、かつ i が taken に含まれていない場合、courses の末尾に (i, w[i]) を追加
  • courses のサイズが k より大きい場合：2番目の要素（重み）で降順にソートし、先頭の k 個だけを残す
  • semester を 1 増やす
  • courses 内の各要素 x に対して：
    • g2[x[0]] 内の各要素 y に対して：g1[y] から x[0] を削除
    • g2[x[0]] を空リストにする
    • x[0] を taken に追加
• 最後に semester を返す

Pythonでの実装例

それでは、実際の実装を見ていきましょう。

def solve(n, relations, k):
    taken = set()
    g1 = [[] for _ in range(n)]
    g2 = [[] for _ in range(n)]
    w = [0] * n
    semester = 0
    for x in relations:
        g1[x[1]-1].append(x[0]-1)
        g2[x[0]-1].append(x[1]-1)

    weight = list(map(len, g1))
    for i in range(n):
        for x in g1[i]:
            w[x] = max(w[x], weight[i])

    while len(taken) < n:
        courses = []
        for i in range(n):
            if (not g1[i]) and (i not in taken):
                courses.append([i, w[i]])
        if len(courses) > k:
            courses = sorted(courses, key=lambda x: x[1], reverse=True)
            courses = courses[:k]

        semester += 1

        for x in courses:
            for y in g2[x[0]]:
                g1[y].remove(x[0])
            g2[x[0]] = []
            taken.add(x[0])
    return semester

n = 6
relations = [(1,3),(2,5),(2,4),(5,6)]
k = 2
print(solve(n, relations, k))

入力

6, [(1,3),(2,5),(2,4),(5,6)], 2

出力

3

まとめ

このプログラムでは、コース間の依存関係を2つの隣接リスト（g1・g2）で管理し、各学期ごとに前提条件が満たされたコースを抽出します。履修候補が上限 k を超える場合は、重み（そのコースを前提とする科目が持つ前提数の最大値）が大きいコースを優先的に選択することで、後続のコースを早く解放できるようにしています。この貪欲な戦略により、全コース修了までの学期数を効率的に最小化できます。