変数のコピーに気をつけろ
変数のコピーを安易にするなよ、って記事です。
初めて僕がこの内容で躓いたのは、
競プロを初めて1か月もたたない頃、最初に深さ優先探索を実装した時のことです。
それがこの問題
初心者ながらに奮闘し、Queryを配列にあらかじめ格納して最後に深さ優先探索で
各頂点に配ってあげるという解法にたどり着き、これならO(N＋Q)となり間に合うはずだ！！と思ったのですが、
いかんせん何度提出してもTLE・MLEになります。その時の解法がこちら
この解法のどの部分がTLEにつながってしまっているか、茶色以上ぐらいの皆さんなら
すぐわかると思うのですが、僕はこの問題のTLEをとろうとするのに何日もの時間を費やしました。
結局一向に答えにたどり着かなかったので、無礼を承知でけんちょんさんにDMで直接質問をすると、
ありがたいことにすぐに返信をいただき、速攻で解決しました。
void dfs_2(int r, int x, vector<int> query, vector<bool> &ald, vector<int> tree, vector<int> &res){ ald[r] = true; x += query[r]; res[r] += x; for (auto p : tree[r]) { if(ald[p] == true){continue;} dfs_2(p, x, query, ald, tree, res); } return; }
はい、引数をすべて値渡しにしていますね。
深さ優先探索では、再帰的に関数が呼び出されるので、引数を値渡しにするとそのたびに引数がコピーされることになります。
エッジの情報を格納しているtree、クエリの情報を格納しているqueryはすべて要素数がNなので、N回呼び出されると計算量はO(N^2)になります。
なのでこれを以下のように、
void dfs_2(int r, int x, const vector<int> &query, vector<bool> &ald, const vector<int> &tree, vector<int> &res){ ald[r] = true; x += query[r]; res[r] += x; for (auto p : tree[r]) { if(ald[p] == true){continue;} dfs_2(p, x, query, ald, tree, res); } return; }
とすると、引数がコピーされず直接参照されるので計算量がぐっと下がります。
もうひとつ、あらかじめグローバル変数としてグラフの情報などを宣言してあげて、
後から内容を受け取ってあげることで、関数の引数に取らなくても深さ優先探索を実行できます。
というかこちらのやり方ほうがスタンダードな気がします。
まあ、当たり前ですね。今更間違えることはないので誰かの役に立つことがあれば幸いです。
と、思ってたんですが、、、、
なんとこの問題で似たようなミスを本日やってしまいました。奇遇にも同じコンテストで、、
これがTLEになったコード。
よく見ると最後のほうの処理で、ある英小文字がどの位置にあるかを管理する
map
バカなんでしょうか。
そのあとの記述を楽にするためと何も考えず書いてしまいましたが、
こちらもたったこの1行のせいで40ms→TLEと計算量が爆増しています。
コンテスト中ならTLEの位置検出のための提出も含めると3ペナですよ。
愚かですね。
皆様も（大半の人には関係ないでしょうが）安易に変数をコピーなさらぬように、、、
セグメント木の配列について
たまにセグ木を配列として持っておきたいことがあります。
atcoder.jp
この問題の想定解はsetの二分探索ですが、
セグ木の配列があればぶん殴ることができます。
僕のライブラリのセグ木はもともと
struct SegmentTree { private: int n; vector<int> node; public: SegmentTree(vector<int> v) { int sz = (int)v.size(); n = 1; while(n < sz) n *= 2; node.resize(2*n-1, 0); for(int i=0; i<sz; i++) node[i+n-1] = v[i]; for(int i=n-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2]; } void update(int x, int val) { // 最下段のノードにアクセスする x += (n - 1); // 最下段のノードを更新したら、あとは親に上って更新していく node[x] = val; while(x > 0) { x = (x - 1) / 2; node[x] = min(node[2*x+1], node[2*x+2]); } } int getsum(int a, int b, int k=0, int l=0, int r=-1) { if(r < 0) r = n; if(b <= l || r <= a) return 0; if(a <= l && r <= b) return node[k]; int vl = getsum(a, b, 2*k+1, l, (l+r)/2); int vr = getsum(a, b, 2*k+2, (l+r)/2, r); return vl + vr; } };
のような感じで、デフォルトコンストラクタ（引数なしで宣言した時に自動でそれにより初期化する）がありませんでした。
この状態で
SegmentTree seg[10];
のようにセグ木の配列を宣言しようとするとコンパイラに猛烈に怒られます。
そこで、
SegmentTree() {
vector<int> v(0);
int sz = (int)v.size();
n = 1; while(n < sz) n *= 2;
node.resize(2*n-1, 0);
for(int i=0; i<sz; i++) node[i+n-1] = v[i];
for(int i=n-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2];
}
というようにデフォルトコンストラクタをstructに追加してあげました。
すると、コンパイルが通り、後からセグ木配列の要素を別のvector
同じように困っている人の一助になれば幸いです。
