ARC043-B:難易度
問の問題があり、それぞれ難易度は である。以下の条件を満たすように 問選ぶときの選び方の数を求めよ。
- 問目の難易度は 問目の難易度の 倍以上である。
- 問目の難易度は 問目の難易度の 倍以上である。
- 問目の難易度は 問目の難易度の 倍以上である。
考え方
DPで求めることができる。問題 を 番目の問題となるように選ぶ選び方を とすると、DP遷移は
となる。愚直にループすると となるが、 については BIT などで区間和を で求めることができるから、全体としては で求めることができる。
※実装のポイントとしては、BITの配列の添字が 番目に対応しているということでしょうか。
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 に応用できる問題にはじめて出会いました。