aoj2383:Rabbit Game Playing

問題文

Rabbit Game Playing | Aizu Online Judge

解法

まずDを昇順にソートする。
Dの先頭からi個(0<=i< N)とって、それらについての通り数をF[i]とする。

条件を満たすあるD[1],...,D[i]の並び替えをとってくる。
この数列にD[i+1]を追加することを考えると、挿入する位置はi+1箇所ある。
このとき、挿入した位置の前後の数字との大小関係が問題になる。
ただ、Dを昇順にソートしているから、挿入位置の前の数字はどうでもよくなって、後ろの数字が重要になる。
後ろにあるやつの数字をdとすれば、d+T>=D[i+1]であればよい。
よって、j<=iかつD[j]+T>=D[i+1]となるjの数とt[i]とすれば、t[i]箇所に挿入できる。
また、末尾には確実に挿入できるので、全体でt[i]+1箇所に挿入できることになる。
D[1],...,D[i]の並び方に関係なくt[i]+1箇所に挿入できるので、F[i+1]=F[i]*(t[i]+1)という漸化式が成り立つ。
また、各iについて、t[i]は尺取り法で計算できる。

よってO(N)

コード

#include<bits/stdc++.h>
using namespace std;

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int mod=1000000007;

int N,T;
int D[100000];
int dp[100010];

signed main(){
    scanf("%lld%lld",&N,&T);
    rep(i,N)scanf("%lld",&D[i]);
    sort(D,D+N);
    dp[0]=1;
    int l=0;
    rep(i,N){
        while(D[l]+T<D[i])l++;
        dp[i+1]=dp[i]*(i-l+1)%mod;
    }
    printf("%lld\n",dp[N]);

    return 0;
}