おはなし

C++を使っている競技プログラマのコードで、よく変数をグローバルに全部置いているのを見かけます。例えばこんなふうに。

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

int N, A[100010]; // 多めに取っておく

int main(){
    cin >> N;
    for(int i = 0; i < N; ++i){
        cin >> A[i];
...

みなさんもこんなコードを書いたことはありませんか？実はそれ、マナー違反なんです！

グローバルに変数をおくことは整頓のできないことを予想させ、マナー違反となります。なるべく変数のスコープを狭くとって整理整頓ができる印象を与えましょう！

本題

というわけでC++競プロerには変数をグローバルに置きっぱなしにしている人が多いです。私もその一人でしたし、蟻本（プログラミングコンテストチャレンジブック：競技プログラミングで有名な参考書）もそのようなサンプルソースが載っています。

ですが、プログラミングの気持ちに立ち返ってこれをみてみると何か変です。やっぱり変数は必要以上に長く生きていてほしくないですし無駄に広いところから見えてほしくないですよね。（ここで、関数については目をつぶることにします関数まで考え始めたら私の頭がおかしくなって死んでしまうので）

なのに、多くの人がグローバルに変数をいっぱい置くコードを書いています。ではそういったコードは競技プログラミングをする上で有利にはたらくのでしょうか、調べてみました！

速度

競技プログラミングは突き詰めると速度を競う競技です（？）。ですから、多少行儀が悪くても速度が早いならその実装を採用する理由になります。果たして速度は早いのでしょうか。

次の問題で試してみましょう。（ネタバレを含みます）

beta.atcoder.jp

次の二つのコードを提出してみます。

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

long long N, ans, x[100010], y[100010];

int main(){
    cin >> N;
    for(int i = 0; i < N; ++i)
        cin >> x[i];
    sort(x, x + N);
    partial_sum(x, x + N, y);
    for(int i = 1; i < N; ++i)
        ans += x[i] * i - y[i - 1];
    cout << ans << endl;
}

#include<bits/stdc++.h>

int main(){
    using namespace std;
    long long N;
    cin >> N;
    vector<long long> x(N), y(N);
    for(int i = 0; i < N; ++i)
        cin >> x[i];
    sort(x.begin(), x.end());
    partial_sum(x.begin(), x.end(), y.begin());
    long long ans(0);
    for(int i = 1; i < N; ++i)
        ans += x[i] * i - y[i - 1];
    cout << ans << endl;
}

下のほうがよりC++としていい書き方っぽい感じがしますが、そのぶん配列を動的に確保していたりするので遅くなってもおかしくない感じがします。

しかし、実際に提出してみると...

このとおり、どちらも同じ実行時間(46 ms)で終了しています。

このことから、グローバルに変数を置いておくこと（と、事前に配列を最大サイズ確保しておくこと）は多くの場合で、劇的な速度の改良をもたらすわけではないということが示唆されます。

それでは、別のところにこれを採用する理由があるのでしょうか。

グラフ系問題と関数

実は、グローバル変数をぽいぽい置いておくことで、少しだけ楽になることがあります。それは、関数を書くときに引数として渡さなくてもよくなるということです。例えば、

vector<vector<int>> edge;

bool check(int hoge){
    ... 
}

int main(){
    ...
    check(hoge);
}

と、

bool check(int hoge, vector<vector<int>>& edge){
    ...
}

int main(){
    vector<vector<int>> edge;
    ...
    check(hoge, edge);
}

だと、確かに少しだけ後者のほうが書くのにコストがかかります。~~我慢して書きなさい~~

まとめ

結局どちらの書きかたのほうがいいのかと言うと、それは今のところ五分五分

ということはなくて、 グローバルに置かなくても困らないものはグローバルに置かないようにするほうがいいのは確定的に明らかです。（もちろん競技ですからその人のしたいようにして結果を出せばよろしいのですけど）

というわけでみなさんも整理整頓のできる競技プログラマであることをソースコードからアピールしていきましょう！

明日の記事は null (枠が空いているのでだれでも書きに来てくださいかなしいことに私は書けません)

競プロをはじめた家事手伝いロボットのブログ

競技プログラミングをしている家事手伝いロボットのブログです

みなさん、競プロをするときにグローバル変数を大量に使っていませんか？実は...

おはなし

本題

速度

グラフ系問題と関数

まとめ