ARC043 B - 難易度

AtCoder やり直し 競技プログラミング

やり直し

B: 難易度 - AtCoder Regular Contest 043 | AtCoder

問題概要

  • 難易度Diの問題がN個ある
  • 以下の条件を満たす4問を選ぶ選び方は何通りか
    • 2 問目の難易度は 1 問目の難易度の 2 倍以上である
    • 3 問目の難易度は 2 問目の難易度の 2 倍以上である
    • 4 問目の難易度は 3 問目の難易度の 2 倍以上である

部分点

4≦N≦3000

満点

4≦N≦105

解法

選ぶ問題を難易度順にa,b,c,dとする。

  • 部分点解法

b,c(b * 2 ≦ c)を固定して考える。

この時aはb/2以下のDiの個数(x個とする)、dは2c以上のDiの個数(y個とする)通りあるのでb,cを固定した時はxy通りある。

これを全てのb,cの組み合わせについて計算して足せばO(N2)で解くことができる。

  • 満点解法

D_iを昇順にソートしておき、二分探索で、 部分点解法と同様に全てのD_iについてそれの半分以下のD_jの個数と2倍以上のD_jの個数を保存しておく。

満点解法ではbを固定して考える。

aは部分点と同じ方法で何通りあるかわかっている。

c,dの組み合わせが何通りあるか。

c=D_iの時、dはD_i * 2 ≦ D_j を満たすD_jである。

例えば、cがD_i以上の時、c,dの組み合わせは、

D_iの2倍以上のD_jの個数+D(i+1)の2倍以上のDjの個数+D(i+2)の2倍以上のDjの個数＋・・・

通りある。これは累積和を用いれば高速に求めることができる。

bごとに最小のcを求め累積和でc,dの組み合わせの数を求めaの個数と掛け算すれば良い。

O(Nlog(N))。

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
const int MOD = 1000000007;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;cin >> N;
  vector<int> D(N); FOR(i,0,N) cin >> D[i];
  sort(D.begin(), D.end());
  int high[N]; CLR(high);
  int low[N]; CLR(low);
  FOR(i,0,N) {
    high[i] = N - (lower_bound(D.begin(), D.end(), D[i] * 2) - D.begin());
    low[i] = upper_bound(D.begin(), D.end(), D[i] / 2) - D.begin();
  }
  int sum[N+1];
  sum[0] = 0;
  FOR(i,0,N) sum[i+1] = (sum[i] + high[i]) % MOD;
  ll ans = 0;
  FOR(i,0,N) {
    int j = lower_bound(D.begin(), D.end(), D[i] * 2) - D.begin();
    ans += (ll)low[i] * (ll)(sum[N]-sum[j]);
    ans %= MOD;
  }
  cout << ans << endl;
  return 0;
}