TechFULの中の人

triple-four’s blog

考察をしよう

こんにちは!Siiiecです。
今回は、考察をすることによってより厳しい制約の問題を解ける例をいくつか紹介したいと思います。

プログラムの実行時間について

本記事で使用されるサンプルプログラムは、C++で書かれています。
実行環境にもよりますが、C++では 10^{8} 回の処理を実行するとおよそ 1 秒の実行時間がかかります。
ただし、処理がどれだけ複雑かにも依存します。

TechFULでC++のプログラムを提出する際は、処理回数が最大でも 10^{8}回程度になるようにすると、TLE(Time Limit Exceeded, 時間切れ)せずにテストケースを通すことができます。

例1 AからBまでの整数の和を求める。

この題材自体は、for文入門の例題として見ることがある問題です。
ここで使う考え方は高校数学でも登場するので馴染み深いと思います。

愚直な実装

問題の通りに、for文で順番に足してみます。

auto ans {0ll};
for (auto i = A; i <= B; ++i)
{
    ans += i;
}

計算量は O(B - A)

この計算では B - A回の加算を行っています。

このままでは A, Bの大きさに比例したループが必要となってしまうため、 B - A = 10^{10}のような場合には、TLEとなってしまいます。

求める和を、図形として考える。

 Aから Bまでの和を図で表したとき、色のついている箇所の面積が求める和となります。
f:id:siiiec:20190326212806p:plain:w200

もう一つ同じ図形を用意すると、四角形の面積を 2で割ったものが求める和となることが分かります。
f:id:siiiec:20190326213540p:plain:w200

計算量はO(1)

 (A + B)(B - A) / 2の式一本で和を求められるため、計算量を落とすことができました!
式をオーバーフローさせずに計算できるならば、 A, Bがどんな値になっても解くことができます。

例2 A + B + C = XとなるA, B, Cの組の数を求める。

 0 \leqq A, B, C, Xとします。

この問題では、forループの回数を減らすことを考えます。

愚直な実装

足して Xということは、 A, B, Cそれぞれの最小値は 0、最大値は Xです。

 A, B, Cそれぞれを 0から Xまで増やして、条件を満たすか判定してみます。

int count{};
for (auto a = 0; a <= x; ++a)
    for (auto b = 0; b <= x; ++b)
        for (auto c = 0; c <= x; ++c)
        {
            if (a + b + c == x)
                ++count;
        }

計算量は O(N^{3})

このままでは、 X = 500程度でも {500^{3} = 125000000 > 10^{8}} 回もの計算が必要になるので、少し大きい入力があるだけでTLEになってしまいます。

式変形をして、計算量を減らす。

 A + B + C = Xを変形すると、 X - A - B = Cとなります。
上記の通り 0 \leqq Cなので、 0 \leqq X - A - Bのとき A, B, Cは条件を満たします。
これによって、 Cのループをなくすことができます。

また、別の形に変形をすると、 B + C = X - Aとなります。
 B \leqq B + C = X - Aより Bの値は X - A以下なので、 Bのループも減らすことができます。

int count{};
for (auto a = 0; a <= x; ++a)
    for (auto b = 0; b <= x - a; ++b)
    {
        if (x - a - b >= 0)
            ++count;
    }

cout << count << endl;

計算量は O(N^{2})

 10^{4} 程度の値までなら、問題なく解けるようになりました!

例3 範囲に対して数を足していく。

以下のような問題を考えます。

 N人の人が生放送を視聴する。
 i番目の人は、時刻 A_iから時刻 B_iまで放送を視聴した。
同時視聴者数の最大値はいくつか?
 0 \leqq A_i, B_i \leqq Tとする。

愚直な実装

それぞれの視聴者が訪れていた時間について、カウントを1ずつ増やします。

// viewers[j] : 時刻jでの視聴者数

// 各視聴者について
for (int i = 0; i < n; ++i)
{
    // A[i]からB[i]までカウントをを1ずつ増やす
    for (int j = A[i]; j <= B[i]; ++j)
    {
        viewers[j] += 1;
    }
}
auto ans = *max_element(viewers.cbegin(), viewers.cend());

計算量は O(NT)

 N, Tがともに大きくなってしまうと、TLEになってしまいます。

imos法

累積和を応用した、要素の重なりを高速に計算する方法です。
視聴を初めた時刻に +1、終了した時刻に -1を格納した時刻分の配列 vを作成し、累積和をとっていきます。

vector<int> v(T + 1);
for (int i = 0; i < n; ++i)
{
    v[A[i]]++;
    v[B[i] + 1]--;
}

int current {};
int ans{};
for (int i = 0; i <= T; ++i)
{
    current += v[i];
    ans = max({ans, current});
}

f:id:siiiec:20190402224507p:plain:w650

計算量は O(N + T)

累積和を使うことで、多くの範囲問題を高速化することができます。

まとめ

僕はプログラミングに慣れるまでは、計算量を意識せずぶん回したせいで実行時間が遅いという経験を何度もしていました。。。
計算量を意識することができると、リソースも有効に使えるようになります。

また考察をして気づくと、難しい問題ほど脳汁ドバドバで気持ちよくなれます。(まだ解けない問題も多いですが。。。)

考察をして気持ちよくなろう!

参考資料

imos法
https://imoz.jp/algorithms/imos_method.html

運営会社 / サービス

444株式会社

triple-four.com

TechFUL

procon.techful.jp