memset TLE#
const int N = 1e8 + 10;
int a[N];
int main()
{
int t; cin >> t;
while (t--) {
memset(a, 0, sizeof a);
...
}
}
memset関数は配列全体を埋めるために使用されますが、複数のデータセットの場合、毎回 a を埋めるため、明らかに TLE になります。
解決策は 2 つあります：
- グローバル変数を廃止する
グローバル変数を廃止することで最大の困難は、関数間での変数の受け渡しの問題です。通常の関数では引数を追加できますが、dfs の場合は不便です。dfs の実装には
lambdaを使用することを検討してください。 memsetを廃止してfill()またはassign()に置き換える不要な操作を省略するだけで、操作回数が合理的な範囲内で要件を満たすようにすればよいです。
筆者はグローバル変数を廃止する方法を好みます。この操作を実現するために、一般的な関数では参照渡しを使用します。以下では、 再帰的なlambda の方法を説明します：
lambda 再帰#
self を使用する -- 最速#
auto dfs1 = [&](auto &self, int u, int p) -> int {
int ret = 1;
for(auto v : adj[u]) {
if(v != p)
ret += self(self, v, u);
}
return ret;
};
self を使用して式自体を指し示し、 auto の推論に方向を指定し、コピーを避けるために参照を使用します。
std::function<> を使用する -- 最も簡単#
このテンプレートクラスは、関数ポインタ、関数オブジェクト、メンバ関数ポインタ、Lambda 式など、呼び出し可能な任意の型のオブジェクトをラップするために使用されます。
#include <functional>
#include <iostream>
void foo(int x) {
std::cout << "foo(" << x << ")" << std::endl;
}
int main() {
std::function<void(int)> f1 = foo;
f1(42);
std::function<void()> f2 = []() { std::cout << "lambda" << std::endl; };
f2();
struct Bar {
void operator()(int x) const {
std::cout << "Bar::operator()(" << x << ")" << std::endl;
}
};
std::function<void(int)> f3 = Bar();
f3(123);
return 0;
}
原理は、このクラスに関数を渡すことです。ただし、大量の再帰呼び出しでは、大量の std::function<> を作成するため、かなりのオーバーヘッドが発生します。
アプローチ：
function<int(int, int)> dfs2 = [&](int u, int p) {
int ret = 1;
for(auto v : adj[u]) {
if(v != p) {
ret += dfs2(v, u);
}
}
return ret;
};
ベンチマーク#
int main() {
int n; cin >> n;
vector<vector<int>> adj(n);
for(int i = 0; i < n - 1; i++) adj[i].push_back(i + 1);
auto dfs1 = [&](auto &self, int u, int p) -> int {
int ret = 1;
for(auto v : adj[u]) {
if(v != p)
ret += self(self, v, u);
}
return ret;
};
function<int(int, int)> dfs2 = [&](int u, int p) {
int ret = 1;
for(auto v : adj[u]) {
if(v != p) {
ret += dfs2(v, u);
}
}
return ret;
};
cout << fixed << setprecision(10);
auto start = clock();
int res1 = dfs1(dfs1, 0, -1);
cout << res1 << '\n';
cout << "Passing self: " << (double) (clock() - start) / CLOCKS_PER_SEC << '\n';
start = clock();
int res2 = dfs2(0, -1);
cout << res2 << '\n';
cout << "std::function: " << (double) (clock() - start) / CLOCKS_PER_SEC << '\n';
assert(res1 == res2);
return 0;
}
/* ---- 結果 ---- */
n = 1e5
Passing self: 0.0000000000
std::function: 0.0180000000
n = 1e6
Passing self: 0.0310000000
std::function: 0.0780000000
n = 2e6
Passing self: 0.0620000000
std::function: 0.1750000000