ARC043-B:難易度

N 問の問題があり、それぞれ難易度は D_1, D_2, ..., D_N である。以下の条件を満たすように 4 問選ぶときの選び方の数を求めよ。

  • 2 問目の難易度は 1 問目の難易度の 2 倍以上である。
  • 3 問目の難易度は 2 問目の難易度の 2 倍以上である。
  • 4 問目の難易度は 3 問目の難易度の 2 倍以上である。

考え方

DPで求めることができる。問題 D_ij 番目の問題となるように選ぶ選び方を dp_{D_i, j} とすると、DP遷移は

 \displaystyle dp_{D_i, j} = dp_{D_i, j} + \sum_{k=1}^{\lfloor\frac{D_i}{2}\rfloor} dp_{k, j-1}

となる。愚直にループすると O(N^2) となるが、 \displaystyle \sum_{k=1}^{\lfloor\frac{D_i}{2}\rfloor} dp_{k, j-1} については BIT などで区間和を O(logN) で求めることができるから、全体としては O(NlogN) で求めることができる。

※実装のポイントとしては、BITの配列の添字が j 番目に対応しているということでしょうか。

       static int m = 100010;
        public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt();
            int[] d = in.nextIntArray(n);
            Arrays.sort(d);

            BIT[] bit = new BIT[5];
            for (int i = 0; i < 5; i++) {
                bit[i] = new BIT(m);
            }

            bit[0].add(0, 1);
            for (int i = 0; i < n; i++) {
                for (int j = 1; j < 5; j++) {
                    int v = d[i] / 2;
                    int u = bit[j-1].query(v);
                    bit[j].add(d[i], u);
                }
            }

            out.println(bit[4].query(100000) % MOD);

        }

ポイント

  • DPの遷移を考える
  • 前の状態に依存するのでDPを考える

類題

雑記

BIT を DP に応用できる問題にはじめて出会いました。