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

# はじめに

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

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">Just10Game Ver 1.0.0です！！！<a href="https://twitter.com/hashtag/Just10Game?src=hash&amp;ref_src=twsrc%5Etfw">#Just10Game</a><a href="https://twitter.com/hashtag/OpenSiv3D?src=hash&amp;ref_src=twsrc%5Etfw">#OpenSiv3D</a> <a href="https://t.co/AnHVxYuKbB">pic.twitter.com/AnHVxYuKbB</a></p>&mdash; れれ (@HitsujiRere) <a href="https://twitter.com/HitsujiRere/status/1243791294679240711?ref_src=twsrc%5Etfw">March 28, 2020</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

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

# どこに用いる

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/422071/ef3eee71-f80d-c5ea-c5ba-d78357c4aa5f.png)

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/422071/a4f2e844-8723-b8c8-74ed-eab01046b7af.png)

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

# コードを考える

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

```cpp
int width = 20;
int height = 20;
```

とし，
マス目の数字を

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

とします．

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

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

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

## 0. そのまま

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

```cpp
// 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. 累積和

まず，

```cpp
// 範囲内の値を全て足す
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 

具体的には，こういった処理になります．
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/422071/8c56b2e6-f85b-b6be-724d-78ac8f27b55c.png)

```cpp
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];
    }
}
```

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

```cpp
// 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. しゃくとり法

さらに高速化するべく，

```cpp
// 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

これを用いると，

```cpp
// 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)$になるという方法です．

後処理として

```cpp
// 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];
    }
```

をしてあげることで，

```cpp
// 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   |

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