競プロを自作ゲームに活用する

はじめに

私は，4月・5月にC++ライブラリのOpenSiv3Dを用いて，Just10Gameというゲームを制作しました．

Just10Game Ver 1.0.0です！！！#Just10Game#OpenSiv3D pic.twitter.com/AnHVxYuKbB

— れれ (@HitsujiRere) March 28, 2020

このゲームを制作するにあたり，ある処理を高速化するために競プロで学んだ知識を用いました．

どこに用いる

この画像は，ゲームの一部分の処理を表したものですが，
赤い四角で囲った部分に競プロで学んだ知識を生かしました．

この部分を詳しく説明すると，例として4×4の数字が書かれたマスがあり，それらを四角で囲んだときに「ちょうど10になる」範囲を求めたいということです．
また，それぞれのマスにおける囲まれた回数もスコア計算のために知りたいとします．

コードを考える

仮に，マスの横幅・縦幅を

int width = 20;
int height = 20;

とし，
マス目の数字を

vector<vector<int>> datas(height, vector<int>(width));

とします．

そして，
ちょうど10の四角形に入る回数を

vector<vector<int>> just10times(height, vector<int>(width));

という配列に入れるとします．

0. そのまま

これを，そのまま全探索するコードを書くと，

// 0 <= beginY < endY <= heightを満たすすべてのbeingY,endYをループ
for (int beginY = 0; beginY < height; ++beginY)
    for (int endY = beginY + 1; endY <= height; ++endY)
    {
        // 0 <= beginX < endX <= widthを満たすすべてのbeingX,endXをループ
        for (int beginX = 0; beginX < width; ++beginX)
            for (int endX = beginX + 1; endX <= width; ++endX)
            {
                // 範囲内の値を全て足す
                int sum = 0;
                for (int x = beginX; x < endX; ++x)
                    for (int y = beginY; y < endY; ++y)
                    {
                        sum += datas[y][x];
                    }

                if (sum == 10)
                {
                    // 範囲内のjust10Timesの要素全てに1を足す
                    for (int x = beginX; x < endX; ++x)
                        for (int y = beginY; y < endY; ++y)
                        {
                            just10times[y][x]++;
                        }
                }
            }
    }

といったコードになり，計算量は$O(W^3H^3)$となります．

実際に実行してみると，21[ms]と非常に遅いことが分かります．

1. 累積和

まず，

// 範囲内の値を全て足す
int sum = 0;
for (int x = beginX; x < endX; ++x)
    for (int y = beginY; y < endY; ++y)
    {
        sum += datas[y][x];
    }

を高速化していきたいと思います．

ここで累積和の2次元累積和という考えを用います．

累積和/2次元累積和に関しては，こちらの記事が分かりやすいのでおすすめします．

累積和を何も考えずに書けるようにする！
https://qiita.com/drken/items/56a6b68edef8fc605821

具体的には，こういった処理になります．

vector<vector<int>> csum(height + 1, vector<int>(width + 1));
// 累積和をとる
for (int y = 0; y < height; ++y)
{
    for (int x = 0; x < width; ++x)
    {
        csum[y+1][x+1] = csum[y][x+1] + csum[y+1][x] - csum[y][x] + datas[y][x];
    }
}

という前処理をしてあげることで，

// beginY < endY <= heightを満たすすべてのbeingY,endYをループ
for (int beginY = 0; beginY < height; ++beginY)
    for (int endY = beginY + 1; endY <= height; ++endY)
    {
        // beginX < endX <= widthを満たすすべてのbeingX,endXをループ
        for (int beginX = 0; beginX < width; ++beginX)
            for (int endX = beginX + 1; endX <= width; ++endX)
            {
                // 範囲内の値の合計を求める
                int sum = csum[endY][endX] - csum[endY][beginX] - csum[beginY][endX] + csum[beginY][beginX];

                if (sum == 10)
                {
                    // 範囲内のjust10Timesの要素全てに1を足す
                    for (int x = beginX; x < endX; ++x)
                        for (int y = beginY; y < endY; ++y)
                        {
                            just10times[y][x]++;
                        }
                }
            }
    }

といったコードになりました．

このコードの（最悪）計算量は前と同じく$O(W^3H^3)$ですが，
実行時間が1.5[ms]と前回の7%にもなりました．

2. しゃくとり法

さらに高速化するべく，

// beginX < endX <= widthを満たすすべてのbeingX,endXをループ
for (int beginX = 0; beginX < width; ++beginX)
    for (int endX = beginX + 1; endX <= width; ++endX)
    {
        ......
    }

を改良します．

しゃくとり法に関しても，こちらの記事が分かりやすいです．

しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ
https://qiita.com/drken/items/ecd1a472d3a0e7db8dce

これを用いると，

// beginY < endY <= heightを満たすすべてのbeingY,endYをループ
for (int beginY = 0; beginY < height; ++beginY)
    for (int endY = beginY + 1; endY <= height; ++endY)
    {
        // しゃくとり法でbeingX,endXをループ
        int beginX = 0, endX = 1;
        while (beginX < width - 1 && endX < width)
        {
            // 範囲内の値の合計を求める
            int sum = csum[endY][endX] - csum[endY][beginX] - csum[beginY][endX] + csum[beginY][beginX];
            if (sum > 10)
            {
                beginX++;
            }
            else if (sum == 10)
            {
                // 範囲内のjust10Timesの要素全てに1を足す
                for (int y = beginY; y < endY; ++y)
                    for (int x = beginX; x < endX; ++x)
                    {
                        just10times[y][x]++;
                    }
                beginX++;
                endX++;
            }
            else // sum < 10
            {
                endX++;
            }
        }
    }

となります．

（最悪）計算量は$O(W^2H^3)$となり，
実際に実行してみると，0.30[ms]と最初の1.4%，前回の20%となりました．

3. いもす法

最後に，いもす法を用います．

いもす法とは，累積和のアルゴリズムを多次元，多次数に拡張したものです．
https://imoz.jp/algorithms/imos_method.html

今回は，#次元の拡張の項にある内容を用います．

$W×H$のマスにおいて，$N$個の範囲内のマスに，1マスずつ数字を足すなどしていると，$O(NWH)$ですが，
先にそれらの差分だけ足し引きし，後に累積和を行うことで，$O(N+WH)$になるという方法です．

後処理として

// x方向へ加算
for (int y = 0; y < height; ++y)
    for (int x = 1; x < width; ++x)
    {
        just10times[y][x] += just10times[y][x - 1];
    }
// y方向へ加算
for (int y = 1; y < height; ++y)
    for (int x = 0; x < width; ++x)
    {
        just10times[y][x] += just10times[y - 1][x];
    }

をしてあげることで，

// beginY < endY <= heightを満たすすべてのbeingY,endYをループ
for (int beginY = 0; beginY < height; ++beginY)
    for (int endY = beginY + 1; endY <= height; ++endY)
    {
        // しゃくとり法でbeingX,endXをループ
        int beginX = 0, endX = 1;
        while (beginX < width - 1 && endX < width)
        {
            // 範囲内の値の合計を求める
            int sum = csum[endY][endX] - csum[endY][beginX] - csum[beginY][endX] + csum[beginY][beginX];
            if (sum > 10)
            {
                beginX++;
            }
            else if (sum == 10)
            {
                // 差分を加算（いもす法）
                just10times[beginY][beginX]++;
                if (endX < width)
                    just10times[beginY][endX]--;
                if (endY < height)
                    just10times[endY][beginX]--;
                if (endX < width && endY < height)
                    just10times[endY][endX]++;

                beginX++;
                endX++;
            }
            else // sum < 10
            {
                endX++;
            }
        }
    }

となりました．

計算量は$O(WH^2)$となりましたが，実行時間は0.34[ms]と先ほどの110%となってしまいました．
（この増加については後述）

まとめ

最終的に，処理に

累積和 → しゃくとり法 → いもす法

といったテクニックを用いることで，高速化できました．

改善まとめ

[ms]	20x20	50x50	100x100
0.そのまま	21	2,600	160,000
1.累積和	1.51	31	480
2.しゃくとり法	0.303	2.57	20.9
3.いもす法	0.338	2.63	21.6

おまけ

[ms]	20x20	50x50	100x100
2.しゃくとり法	0.303	2.57	20.9
3.いもす法	0.338	2.63	21.6

ですが，サイズを大きくすれば，3.いもす法の方が高速になりそうです．

以下全て500x500

[ms]	全て1，Just250	1~5，Just250	1~5，Just500
2.しゃくとり法	4,230	2,510	2,740
3.いもす法	2,390	2,350	2,360

ありがとうございました。