ABC106: D - AtCoder Express 2

問題概要

の個の数の組が与えられる。を満たすそれぞれのについてかつを満たすの個数を求めよ。

(問題文は https://beta.atcoder.jp/contests/abc106/tasks/abc106_d に記載されている。)

制約

• 
• 
• 
• 
• 

アイディア

の制約がと小さいことに注目する。

とりあえず，次のような表を作ることを考える。

行目の列目にはかつを満たすの個数が入っている。

例えば「入力例 3」を例に取ると，表は以下のようになる。

そして，この表の行目の列目の要素をと表すことにすると，クエリに対する答えはとなる。

例えば「入力例 3」のつ目のクエリに対する答えは，下の表の黒く塗られたセルの値の和になる。

すべての考えられる答えを2次元累積和によって先に求めておくこともできるが，ここではクエリごとにメモ化再帰で求めることを考える。

メモ化再帰をするためにに関する漸化式をたてる。

「入力例 3」のつ目のクエリで考えると以下のようになる。

(配色が悪くてごめんなさい... 紫色の部分は赤色と青色が重なっていると考えてください。)

上の図で，黒色に塗られた部分はである。また，赤色(紫色を含む)部分はとなっていて，青色(紫色を含む)部分はとなっている。さらに，赤色と青色が重なって紫色になっている部分はとなっている。

ここから求めたい部分は赤色(紫色を含む)部分と青色(紫色を含む)部分の和からダブルカウントした紫色部分を引いたところに黒色の部分を足したものであることがわかるので，となることがわかる。

さらに，これを一般化するととなる。なお，ここでまたはのときとしておくと便利である。

実装

最初にすべてのについてとし，のそれぞれについてにを加える。

次にすべてのについてに初期化しておく(理由は後述する)。

そして，次のような関数を考える。

1. またはのときを返して終了する。

2. のとき を計算してに格納する。

3. を返して終了する。

ここで最初にとする理由は「のときにすでにを計算済みである」ようにして，すべてのについてを1回のみ計算し，あとは保存済みの計算結果を返すようにすることで計算量をにするためである。

このような関数を実装した上で，あとはを満たすそれぞれのについてを求めるのみである。

最終的に計算量は。

コード

#include "bits/stdc++.h"
using namespace std;

int N,ans[555][555],t[555][555];

int solve(int p, int q){
    if(p > N || q == 0){
        return 0;
    }
    if(ans[p][q] == -1){
        ans[p][q] = solve(p,q-1) + solve(p+1,q) - solve(p+1,q-1) + t[p][q];
    }
    return ans[p][q];
}

int main(void){
    int M,Q,i,L,R,p,q;
    fill(t[0],t[555],0);
    fill(ans[0],ans[555],-1);
    cin >> N >> M >> Q;
    for(i=0; i<M; ++i){
        cin >> L >> R;
        ++t[L][R];
    }
    for(i=0; i<Q; ++i){
        cin >> p >> q;
        cout << (solve(p,q)) << endl;
    }
    return 0;
}

(提出したものはこちら)

注意点

Python3で提出した際に(おそらく再帰の深さの上限を超えたせいで)REが出ました。