Pythonで重ならないk本の線分の組み合わせ数を求めるプログラム

問題の概要

数直線上にn個の点が並んでいるとします。i番目の点(0からn-1まで)は、位置x = iに配置されています。このとき、ちょうどk本の異なる線分を、互いに重ならないように引く方法が何通りあるかを求めるのがこの問題です。ただし、各線分は2つ以上の点をカバーする必要があります。

主な条件を整理すると、次のようになります。

• 各線分の両端点は整数座標でなければならない
• k本の線分は、与えられたn個の点をすべてカバーする必要はない
• 線分同士は端点を共有してもよい(内部が重ならなければよい)
• 答えが大きくなりすぎる場合は、10^9 + 7で割った余りを返す

入力例と出力例

たとえば、n = 4、k = 2が入力として与えられた場合、出力は5になります。実際、次の5通りの線分の組み合わせを作ることができます。

• (0〜2)と(2〜3)
• (0〜1)と(1〜3)
• (0〜1)と(2〜3)
• (1〜2)と(2〜3)
• (0〜1)と(1〜2)

解き方のアプローチ(動的計画法)

この問題は、動的計画法(DP)を用いて解きます。隣り合う点同士をつなぐ区間ごとに「その区間をどの線分が使うか」を順番に決めていき、全体でちょうどk本になる組み合わせを数え上げます。

具体的な手順は以下の通りです。

• 剰余を取るための法を m = 10^9 + 7 とする
• n = n - 1 として調整する(扱うのは隣接点間の区間のため)
• 関数 dp(i, covered, j) を定義する。i は現在見ている点の位置、covered は直前の点まで線分が続いているかどうか、j はそこまでに確定した線分の本数を表す
• i が n に到達したら、j が k と一致していれば 1(true)、そうでなければ 0(false)を返す
• j が k を超えていたら 0 を返す(それ以上探索しても無意味なため)
• ans = dp(i + 1, False, j) + dp(i + 1, True, j + 1) を計算する(区間を使わない場合+新しい線分を始める場合)
• covered が true の場合は、さらに ans += dp(i + 1, True, j)(既存の線分を延長する場合)を加える
• 最後に ans mod m を返す
• メイン側では dp(0, False, 0) の結果を返す

状態遷移のポイント

各区間(隣接する2点をつなぐ辺)に対しては、「使わない」「新しい線分の始まりにする」「進行中の線分を延長する」という選択肢があります。covered フラグによって線分を延長できるかどうかを管理することで、線分が端点を共有するケースも正しく数えることができます。

Pythonでの実装例

以下が実際の実装コードです。

def solve(n, k):
    m = 10 ** 9 + 7
    n -= 1

    def dp(i, covered, j):
        if i == n:
            return j == k
        if j > k:
            return 0
        ans = dp(i + 1, False, j) + dp(i + 1, True, j + 1)
        if covered:
            ans += dp(i + 1, True, j)
        return ans % m

    return dp(0, False, 0)

n = 4
k = 2
print(solve(n, k))

入力

4, 2

出力

5

補足:計算量について

上記の実装は素朴な再帰のため、nが大きくなると計算時間が指数的に増加します。Pythonの functools.lru_cache デコレータを dp 関数に付けるとメモ化が有効になり、状態数は O(n × k × 2) 程度に抑えられるため、大きな入力でも高速に動作するようになります。競技プログラミングなどで制約が厳しい場合は、メモ化の追加を検討するとよいでしょう。