変数のコピーに気をつけろ - sote2の競プロメモ

変数のコピーを安易にするなよ、って記事です。

初めて僕がこの内容で躓いたのは、
競プロを初めて1か月もたたない頃、最初に深さ優先探索を実装した時のことです。

それがこの問題

初心者ながらに奮闘し、Queryを配列にあらかじめ格納して最後に深さ優先探索で
各頂点に配ってあげるという解法にたどり着き、これならO(N＋Q)となり間に合うはずだ！！と思ったのですが、
いかんせん何度提出してもTLE・MLEになります。その時の解法がこちら

atcoder.jp

この解法のどの部分が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;
}