ARC043 B - 難易度

B - 難易度

概要

N項の数列Dが与えられる。この数列から4項を非復元抽出する。
この4項が を満たすような抽出方法は何通りあるか。
（問題だと数列Dは「コンテストの問題の難易度」と対応）

制約

4 ≦ N ≦ 10^5
1 ≦ di ≦ 10^5

方針

下記のDP配列を考える。
dp[i][j]：問題数がj、最後の問題がi番目のときの問題セットの通り数
このときDPは下記のように遷移する。

このDPをそのまま計算すると、j, i, kのループが必要となり間に合わない。
そこで、Σ計算部分を工夫する。

添字kに注目する。
あるiについて、dp[i][j]を計算する際にdp[k][j-1]が足されるとすると、
i' ≧ i なる i' についてdp[i'][j]を計算するときにもdp[k][j-1]が足される。
よって、dp[k][j-1]が足される最小のiを見つけ、そこに足したら後は累積和で計算する。

感想

下記を参考にしました。
ry0u.github.io

調べるといろいろな解き方があり、興味深いです。

解答

Submission #4627464 - AtCoder Regular Contest 043

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
const ll MOD = 1e9 + 7;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N;
	cin >> N;
 
	vector<ll> d(N, 0);
	rep(i, N) cin >> d[i];
	sort(d.begin(), d.end());
 
	vector<vector<ll>> dp(100001, vector<ll>(4, 0));
	rep(i, N) dp[i][0] = 1;
 
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < N; j++){
			if(d[j] * 2 > d[N-1]) continue;
 
			int id = lower_bound(d.begin(), d.end(), d[j] * 2) - d.begin();
			dp[id][i+1] += dp[j][i];
			dp[id][i+1] %= MOD;
		}
 
		for(int j = 1; j < N; j++){
			dp[j][i+1] += dp[j-1][i+1];
			dp[j][i+1] %= MOD;
		}
	}
 
	ll ans = 0;
	for(int i = 0; i < N; i++){
		ans += dp[i][3];
		ans %= MOD;
	}
 
	cout << ans << endl;
 
}