【AtCoder】「分野別　初中級者が解くべき過去問精選 100 問」解答例【幅優先探索】

この記事は【AtCoder】初中級者が解くべき過去問精選 100 問を緑色コーダーが C++ で解いてみたの子記事です。お読みになる前に親記事をご確認ください。

28. ALDS_11_C – 幅優先探索
29. AtCoder Beginner Contest 007 C – 幅優先探索
30. JOI 2011 予選 5 – チーズ
31. JOI 2012 予選 5 – イルミネーション
32. AOJ 1166 – 迷図と命ず
33. AtCoder Beginner Contest 088 D – Grid Repainting

28. ALDS_11_C – 幅優先探索

問題へのリンク

幅優先探索についての以下の知識を問う問題です。

辺ごとの距離が等しい場合、幅優先探索を行うと始点からの最短距離が求められること
実装方法

BFS (幅優先探索) 超入門！〜キューを鮮やかに使いこなす〜の「1-2. BFS の実装」の BFS の実装テンプレを参考にすると解答できます。
計算量は $O(\sum_{i = 1}^n k_i) = O(n^2) = 10^4$ 程度です。

解答例

29. AtCoder Beginner Contest 007 C – 幅優先探索

問題へのリンク

幅優先探索をグリッドで表現された迷路に対して行う問題です。
幅優先探索によって最小移動手数を算出できることを問題文が説明しているため、幅優先探索の理解の助けになると思います。
計算量は $O(RC) = 10^4$ 程度で、実行時間制限を満たして解答できます。

解答例

30. JOI 2011 予選 5 – チーズ

問題へのリンク

下記の問題文の記述から、ねずみが工場に訪れる順番は生産するチーズが柔らかい順の一通りに絞られます。

硬さ $1$ から $N$ までのチーズを生産するチーズ工場がちょうど $1$ つずつある．

ねずみの最初の体力は $1$ であり，チーズを $1$ 個食べるごとに体力が $1$ 増える．ただし，ねずみは自分の体力よりも硬いチーズを食べることはできない．

訪れる順序が決まるため、問題をいくつかの最短経路問題に分割できます。 $i$ を $1 \leq i \leq N$ の整数、便宜的に硬さ $0$ のチーズを生産する工場を巣としたとき、以下の $N$ 個の最短経路問題の答えの和が問題の答えです。

硬さ $i - 1$ のチーズを生産する工場から硬さ $i$ のチーズを生産する工場までの最短経路問題

それぞれの最短経路問題を幅優先探索を使って解くと計算量は $O(HW)$ になります。全体の計算量は $O(HWN) = 10^7$ 程度です。

解答例

31. JOI 2012 予選 5 – イルミネーション

問題へのリンク

地図の外側は自由に往来できることを表現するために東西南北の四方を建物がない正六角形で囲み、地図を $W \times H$ から $(W + 2) \times (H + 2)$ に拡張します。その際、元の問題の添字 (1-based) を 0-based な添字だとみなし、北と西に座標が $(x, 0), (0, y)$ である建物がない正六角形を用意すると、拡張による添字の混乱が減らせるかと思います。

複数の異なる白色の正六角形 (建物がない正六角形) が同じ壁に接することはありません。そのため、拡張した地図の北西から深さ優先探索もしくは幅優先探索で建物がない正六角形を探索し、それぞれの正六角形で壁の個数を数えて和をとると答えになります。北西から始める理由は、地図を拡張したことにより北西の正六角形には建物がないことが分かるためです。

下記のような関数を用意すると、探索中の正六角形の座標から隣接する正六角形の座標を列挙することが多少楽になります。

pair<int, int> adjacent_xy(int x, int y, int i) // i は隣接する正六角形の番号
{
    int dy[] = {0, -1, -1, 0, 1, 1};
    int dx1[] = {1, 1, 0, -1, 0, 1};
    int dx2[] = {1, 0, -1, -1, -1, 0};
    if (y % 2 == 1)
        return {x + dx1[i], y + dy[i]};
    return {x + dx2[i], y + dx[i]};
}

計算量は $O(WH) = 10^4$ 程度です。

解答例 1

JOIの解説にスタック (コールスタック) について下記の記述があります。

再帰を用いて大きな領域を塗りつぶす場合は，スタックメモリが溢れないように幅優先探索を用いて塗りつぶしを行わなければならない．

そのため、再帰関数によるスタックメモリの使用量の見積方法を調べました。不十分な気もしますが、分かったことについてメモします。

コールスタックについては以下の資料などに説明があります。

プログラムはスタックに関数を実行するための引数やローカル変数などの情報 (スタックフレーム、関数アクティベーションレコード) を記録する領域を確保します。

スタックメモリが溢れることについては Wikipedia のスタックオーバーフローのページや APG4b V – 2.05.再帰関数に記載があります。下記は Wikipeida の方からの引用です。

コールスタックに蓄積されるデータ量が限界を超えるとスタックは「オーバーフロー」し、未定義動作を引き起こす。オペレーティングシステムにもよるが、プログラム側で対策をとっていなければ通常はプロセスがクラッシュしてしまう。ただし、スタックオーバーフローの原因となりうるコードパターンは比較的限定されている。

スタックオーバーフローの発生原因のうち、最も多いのはサブルーチンの再帰呼び出しによる無限ループ（無限再帰）である。また、ソースコードの設計上は無限再帰ではなく、終了条件を決めて有限回数で打ち切るような有限再帰になっていたとしても、再帰呼び出しの階層数が深すぎると実行環境におけるコールスタックの上限を超えてしまい、スタックオーバーフローとなってしまう場合もある。

プログラムについて下記の情報が分かれば、スタック領域の使用量の見積ががある程度できそうです。

プログラム実行時のスタックメモリのサイズ
再帰関数 $1$ 回の実行に必要なスタックフレームのサイズ
再帰関数の呼び出し回数

上記の 1, 2 についてプログラミング言語 C++, コンパイラ gcc に限定して調べたことを記載します。

プログラム実行時のスタックメモリのサイズ

AtCoder の各問題にはメモリ制限が記載されています。スタックサイズについては chokudai さんの tweet によると制限を廃止したそうです。そのため、メモリの総利用量がメモリ制限に違反するかどうかを考えれば十分であるようです。
確認のため、再帰関数がスタックメモリを圧迫するプログラムを用いた実験を行いました。下記に実験結果のリンクを貼ります。どちらの問題も問題記載のメモリ制限までは問題なく実行できることが確認できます。

AOJ については Judge’s Replies の「Adjustment for different languages」によるとスタック制限は $64$ MB のようです。ただし、下記の注意が記載されているため、スタックの制限を確認したい場合は上記 web ページを直接ご確認ください。

Please note that the Stack Limit can be subject to change in the future.

再帰関数 $1$ 回の実行に必要なスタックフレームのサイズ

gcc では -fstack-usage オプションを使うと関数単位でスタックの利用量を取得できます。下記のようにオプションをつけて main.cpp というソースファイルをコンパイルすると main.su という関数ごとのスタックの利用量が記載されたファイルが作成されます。

$ g++ -fstack-usage main.cpp

-fstack-usage を使わずにコードからスタックの利用量を見積もることに挑戦しましたが、私にはできませんでした。そのため、以降 -fstack-usage を使います。

以上をもとに解答例 1 の再帰関数 dfs のスタックの利用量を見積もってみます。
解答例 1 を -O2 と -fstack-usage を付けてローカルでコンパイルして得られる関数単位のスタック利用量は下記の通りです。

/usr/local/Cellar/gcc/10.2.0/include/c++/10.2.0/bits/locale_facets.h:1084:7:virtual std::ctype<char>::char_type std::ctype<char>::do_widen(char) const  8   static
main.cpp:4:16:std::pair<int, int> adjacent_xy(int, int, int)    8   static
main.cpp:14:5:int dfs(int, int, int (*)[102], bool (*)[102], int, int, int) 96  dynamic,bounded
main.cpp:32:5:int main()    52144   dynamic,bounded
main.cpp:45:1:cpp)  16  static

再帰関数 dfs は $1$ 回の呼び出しに $96$ Byte かかることがわかりました。

この深さ優先探索では各正六角形を一度しか探索しないため、最悪でも $O(WH) = 10^4$ 程度しかスタックに dfs のスタックフレームを積みません。 $96 \times 10^4$ Byte は $1$ MB 程度であるため、メモリ制限に違反しません。

スタック領域の枯渇が気になる方には STL の stack を用いた深さ優先探索の実装や幅優先探索を使った解法もあります。解法自体 (建物がない正六角形に移動して、壁の枚数を数える) と計算量のオーダーはどのやり方でも大して変わらないため、解答例のみ掲載します。

解答例 2 stack を用いた深さ優先探索
解答例 3 幅優先探索

32. AOJ 1166 – 迷図と命ず

問題へのリンク

幅優先探索を行って最短経路を求める問題です。隣接する四角に移動可能かを判定するのに (実装上の) 工夫が必要です。

壁の情報の保持の仕方ですが、縦の壁と横の壁を別の変数で持つと 1 行の要素数が揃い多少楽です。
入力時には下記のように $2$ 行単位で $1$ つめの for 文を回すと別々の変数に入力を分離できます。

int w, h;
cin >> w >> h;
int wall_vert[30][30] = {};
int wall_hori[30][30] = {};
for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w - 1; ++j)
        cin >> wall_vert[i][j];
    if (i == h - 1)
        continue;
    for (int j = 0; j < w; ++j)
        cin >> wall_hori[i][j];
}

移動可能か判定する関数は例えば下記のように実装できます。

bool can_go(int h, int w, int wall_vert[30][30], int wall_hori[30][30],
            int x, int y, int dx, int dy) // dx, dy は移動の差分
{
    assert(-1 <= dx && dx <= 1);
    assert(-1 <= dy && dy <= 1);
    assert(dx == 0 || dy == 0);
    int x2 = x + dx, y2 = y + dy;
    if (x2 < 0 || h <= x2 || y2 < 0 || w <= y2) // 迷路の外側判定
        return false;
    if (dx > 0 && wall_hori[x][y] == 1) // 下への移動判定
        return false;
    if (dx < 0 && wall_hori[x2][y] == 1) // 上への移動判定
        return false;
    if (dy > 0 && wall_vert[x][y] == 1) // 右への移動判定
        return false;
    if (dy < 0 && wall_vert[x][y2] == 1) // 左への移動判定
        return false;
    return true;
}

後は最短経路の長さの数え方から始点の最短経路を $1$ それ以外を $0$ と初期値を設定した後、幅優先探索を行えば求解できます。

$1$ つのデータセットに対する計算量は $O(hw) = 10^3$ 程度で高々 $100$ データセットしかないため、制限時間内に求解できます。