読者です 読者をやめる 読者になる 読者になる

hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

AtCoder Regular Contest 043 B: 難易度

AtCoder 動的計画法 数え上げ

ARC043 B問題、データ構造で殴ってしまったけど、明らかに想定解法より楽な方法だと思うのでいちおう紹介。

問題概要

問題原文 → B: 難易度 - AtCoder Regular Contest 043 | AtCoder

長さ  N の数列が与えられる。この数列から、(  i - 1 番目に取った数 )  \times 2 \leqq (  i 番目に取った数 ) となるように数字を  4 つとる。この取り方の総数を  1000000007 で割った余りを出力せよ。なお、同じ値でも違うインデックスにある数同士は区別される。

解説

まず数列をソートして、dp でできないかを考えてみます。

dp[i][j] := i 番目の数を j 番目に使う場合の数 という配列を考えると、 a_i の前に選んだ可能性のある数は  1 \leqq a_k \leqq \lfloor \frac{a_i}{2} \rfloor を満たす全ての数であるため、遷移は以下のようになります。

 dp_{i,j} = dp_{i,j} + \sum_{1 \leqq a_k \leqq \lfloor \frac{a_i}{2} \rfloor} dp_{k, j-1}

これをそのまま実装してしまうと  O(N^2) のコードになってしまい TLE しますが、  \Sigma をとっている部分は  a のインデックスが  0 からある数字までの区間の和ですので、この部分を BIT などのデータ構造で高速で計算すれば時間内に解くことができます。計算量は  O(N \log N) です。実装では BIT を使いやすくするために配列を再利用するとよいでしょう。

ソースコード

BIT を使いやすくするために配列の再利用をしています。

// BIT 略
signed main() {
    int n; cin >> n;
    int a[100010]; rep(i,0,n) cin >> a[i];
    sort(a, a+n);
    zeroIndexedBIT<int> dp(n);
    rep(i,0,n) dp.add(i, 1);

    rep(j,0,3) {
        repr(i,n-1,0) {
            dp.add(i, -dp.sum(i,i));
            int k = upper_bound(a, a+n, a[i] / 2) - a;
            k--;
            if(k < 0) continue;
            int temp = dp.sum(0, k);
            dp.add(i, temp);
        }
    }

    int ans = dp.sum(0, n-1);
    cout << ans << endl;
    return 0;
}