C++で有効な集荷・配達シーケンスの総数を数える方法

問題の概要

n件の注文からなるリストがあるとします。各注文には「集荷（P）」と「配達（D）」の2つのサービスが含まれています。ここでの目的は、配達[i]が必ず集荷[i]よりも後に行われるという制約を満たす、すべての有効な集荷・配達の順列を数えることです。

答えは非常に大きな値になる可能性があるため、結果は 10^9 + 7 で割った余りを返します。

入力例と出力例

たとえば、入力が 2 の場合、出力は 6 になります。考えられるすべての有効な順序は次のとおりです。

• (P1, P2, D1, D2)
• (P1, P2, D2, D1)
• (P1, D1, P2, D2)
• (P2, P1, D1, D2)
• (P2, P1, D2, D1)
• (P2, D2, P1, D1)

一方、(P1, D2, P2, D1) のような順序は、配達2（D2）が集荷2（P2）よりも先に現れているため無効です。

解決のためのアプローチ

この問題は、メモ化再帰（トップダウンDP）を用いて解くことができます。手順は以下のとおりです。

• m := 10^9 + 7（剰余計算に使う法）
• N := 550
• サイズ (N+5) × (N+5) の二次元配列 dp を定義し、すべて -1 で初期化する
• 関数 add(a, b)：((a mod m) + (b mod m)) mod m を返す
• 関数 mul(a, b)：((a mod m) × (b mod m)) mod m を返す
• 関数 solve(inPickup, left, i, j)：
  • i == 0 かつ j == 0 の場合、1 を返す（すべての操作を完了した状態）
  • dp[i][j] が -1 以外の場合、計算済みなので dp[i][j] をそのまま返す
  • ret := 0 で初期化
  • i > 0 の場合（まだ集荷できる注文がある）：ret = add(ret, mul(left, solve(inPickup + 1, left - 1, i - 1, j)))
  • j > i の場合（未配達の集荷済み注文がある）：ret = add(ret, mul(inPickup, solve(inPickup - 1, left, i, j - 1)))
  • dp[i][j] = ret を返す
• メイン処理では solve(0, n, n, n) を呼び出して結果を得る

ポイント： 変数 i は残りの集荷対象の注文数、j は全体で完了していない注文数、inPickup は現在集荷済みでまだ配達されていない注文数、left は選択可能な候補の数を表します。各ステップで「新しい集荷を行う」か「既存の集荷済み注文を配達する」かを選択し、その組み合わせ数を掛け合わせながら合計を求めていきます。

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

C++による実装例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int m = 1e9 + 7;
const int N = 550;
int dp[N + 5][N + 5];
lli add(lli a, lli b){
   return ((a % m) + (b % m)) % m;
}
lli mul(lli a, lli b){
   return ((a % m) * (b % m)) % m;
}
class Solution {
   public:
   void pre(){
      for (int i = 0; i < N; i++) {
         for (int j = 0; j < N; j++) {
            dp[i][j] = -1;
         }
      }
   }
   int solve(int inPickup, int left, int i, int j){
      if (i == 0 && j == 0)
      return 1;
      if (dp[i][j] != -1)
      return dp[i][j];
      int ret = 0;
      if (i > 0) {
         ret = add(ret, mul(left, solve(inPickup + 1, left - 1, i
         - 1, j)));
      }
      if (j > i) {
         ret = add(ret, mul(inPickup, solve(inPickup - 1, left, i,
         j - 1)));
      }
      return dp[i][j] = ret;
   }
   int countOrders(int n){
      pre();
      return solve(0, n, n, n);
   }
};
main(){
   Solution ob;
   cout << (ob.countOrders(2));
}

入力

2

出力

6

まとめ

このように、メモ化再帰を活用することで、配達が対応する集荷の後に必ず行われるという制約を満たす順列の総数を効率的に求められます。状態数は O(n²)、各状態の遷移も定数時間であるため、n が数百程度までの入力でも高速に動作します。