ABC017 D - サプリメント
問題
$ N要素の数列$ f_i (i = 0, 1, 2, \dots, N -1, 1 \leq f_i \leq M)が与えられる。同一の数が含まれないように、1度に1つ以上をはじめからとる。とりかたはいくつあるか?$ 1000000007で割ったあまりを答えよ。
制約
$ 1 \leq N \leq 100,000
$ 1 \leq M \leq 100,000
$ f_iはすべて整数
部分点の制約
$ 1 \leq N \leq 5,000
$ 1 \leq M \leq 5,000
考察
1回目に$ f_1のみをとる場合には、$ f_i (i \geq 2)を使って2回目以降にとる場合の数だけあります。
1回目に$ f_1, f_2をとれて、とった場合には、$ f_i (i \geq 3)を使って2回目以降にとる場合の数だけあります。
何回目であるか、というのは特に関係ありません。こう見ていくと部分問題が見えてきます。
欲しいものは$ f_1以降を使ってとる場合の数で、それは以下のものの和になります。
$ f_2以降を使って取る場合の数(1回目に$ f_1をとる)
$ f_3以降を使って取る場合の数(1回目に$ f_1, f_2をとる)
$ \cdots
$ f_k以降を使って取る場合の数(1回目に$ f_1, f_2, \dots, f_{k-1}をとる)
$ f_1, f_2, \dots, f_{k-1}はすべて異なる。
$ f_i = f_kとなる$ iが$ 1 \leq i \leq k - 1にある。
これを素直にメモ化再帰で実装すると$ O(N^2)で部分点までとることができます。
code:cpp
vector<int> memo(N + 1, -1);
function<int(int)> num = &(int i) { if (i == N) return 1;
if (memoi != -1) return memoi; int res = 0;
unordered_map<int, int> m;
for (int j = i; j < N; ++j) {
if (m[fj]) return memoi = res; res += num(j + 1)
res %= MOD;
}
};
cout << num(0) << endl;
同じことを、$ {\rm dp}_iを$ f_i以降を使うとりかたの場合の数としてDPで書くと以下のようになります。 code:cpp
vector<int> dp(N + 1, 0);
for (int i = N; i >= 0; --i) {
unordered_map<int, int> m;
for (int j = i - 1; j >= 0; --j) {
}
}
満点をとるために、この計算の中に無駄な部分が無いかを探してみます。
$ f_jが重複しない区間を調べていく際に、$ iから左に調べた結果は、$ i - 1から左を調べる際にも利用することが出来ます。
https://gyazo.com/0139120da7099a1a85a7f214699ab86c
つまりしゃくとり法を利用することができます。これで、$ f_jが重複しない区間のみであれば$ O(N)で計算できます。 https://gyazo.com/dc7c281fc1a3c7b53bf8944f735dbc60
以上より$ O(N)でこの問題を解くことができました。
code:cpp
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i) #define all(a) (a).begin(), (a).end() int N, M;
vector<int> f;
const int MOD = 1000000007;
int main() {
cin >> N >> M;
f.resize(N);
vector<int> dp(N + 1, 0);
// (l, r]
auto rangeAdd = &(int l, int r, int x) { if (l >= 0) {
}
};
rangeAdd(N - 1, N, 1);
unordered_map<int, int> m;
int l = N - 1, r = N;
while (r > 0) {
while (l >= 0 && !m[fl]) { --l;
}
do {
--r;
} while (r > l && m[fl]); }
return 0;
}