AOJ 2383 Rabbit Game Playing

問題

Rabbit Game Playing | Aizu Online Judge

数列 D が与えられる。これに関して, 以下の条件を満たす並べ方は何通りあるか求めよ。
条件: 任意の i について, D[i] <= D[i+1]+T が成り立つ。

解法

挿入DP というやつ？

dp[i] = (i 番目までの並べ方の場合の数) というのが分かっているとき, i+1 番目の数を入れられるところは, 今までの並べ方に関係なく決まります(直後の数との差が T 以下なら大丈夫)。

よって, i+1 番目の数を挿入できるところは i+1 - (D[i+1]-T 以上の要素の数) + 1 となるのですが, これは D をソートしておくと高速に計算できます。

解法に気付けば実装は超簡単。

const int MAXN = 100100;
const int MOD = 1e9+7;
ll dp[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, T;
    cin >> N >> T;
    vector<int> D(N);
    for (int i = 0; i < N; i++)
        cin >> D[i];
    sort(D.begin(), D.end());
    dp[0] = 1;
    for (int i = 1; i < N; i++) {
        int j = lower_bound(D.begin(), D.end(), D[i]-T) - D.begin();
        dp[i] = (dp[i-1]*(i-j+1))%MOD;
    }
    cout << dp[N-1] << endl;
    return 0;
}