Algoogle

Algorithm for Programming Contest

AOJ 2383 Rabbit Game Playing

Category: AOJ Tag: implementation

Rabbit Game Playing

問題概要


解法


ステージは難易度順にソートしておく. ステージiの難易度をlevel[i]とする.
ステージiはそれより前のステージのうちどのステージの前にクリアされるかを考える.
その場合の数は明らかにlevel[i]以下かつlevel[i]-T以上の個数.
どのステージの前にも入らない場合を加えてやると, ステージiの場合の数が定まる.
あとはそれを掛けあわせていけば良い.

コード


(2383.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>

#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,a) repi(i,0,a)
using namespace std;

typedef long long ll;

int N, T;
int level[100010];
const int mod = 1000000007;

int main(){
    cin >> N >> T;
    rep(i,N) cin >> level[i];
    sort(level,level+N);
    ll ans = 1;
    rep(i,N) ans = ans * (upper_bound(level,level+i,level[i]) - lower_bound(level,level+i,level[i]-T) + 1) % mod;
    cout << ans << endl;
    return 0;
}

Comments