AtCoder Regular Contest 043 B: 難易度

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

問題概要

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

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

解説

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

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

これをそのまま実装してしまうと のコードになってしまい TLE しますが、 をとっている部分は のインデックスが からある数字までの区間の和ですので、この部分を BIT などのデータ構造で高速で計算すれば時間内に解くことができます。計算量は です。実装では 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;
}