この記事は 【AtCoder】初中級者が解くべき過去問精選 100 問を緑色コーダーが C++ で解いてみた の子記事です。お読みになる前に親記事をご確認ください。
24. ALDS_11_B – 深さ優先探索
深さ優先探索の動作を確認する問題です。レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 の「2-2-2. 12 個の基本アルゴリズムをマスターする！」でも紹介されている DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【前編】、特に「3-3. DFS の再帰関数を用いた実装」の「タイムスタンプ」を参考にします。
参考元「タイムスタンプ」の first_order が本問題の d[v], last_order が f[v] に対応します。参考元のフラグ seen は d[v] で代用できます。d[v] の初期値を -1 とし、発見した時に d[v] に発見した時刻 (正の値) を入れるとすれば、v の発見・未発見は d[v] の正負で判定できるためです。
下記にこの問題の関数 dfs の実装例を記載します。
using Graph = vector<vector<int>>;
void dfs(const Graph &graph, vector<int> &d_vec, vector<int> &f_vec,
int u, int &time)
{
d_vec.at(u) = time++;
for (int v : graph.at(u)) {
if (d_vec.at(v) > 0)
continue;
dfs(graph, d_vec, f_vec, v, time);
}
f_vec.at(u) = time++;
}
下記の問題文の記述はグラフが非連結の場合の処理の仕様です。
探索は元の始点から到達可能なすべての頂点を発見するまで続き、未発見の頂点が残っていれば、その中の番号が一番小さい１つを新たな始点として探索を続けます。
以下のように for 文を使って、未発見の頂点から順に関数 dfs を実行すると、上記の仕様通りにすべての頂点を漏れなく発見できます。
int u;
int time = 1;
vector<int> d_vec(n, -1), f_vec(n, -1);
for (int u = 0; u < n; ++u) {
if (d_vec.at(u) > 0)
continue;
dfs(graph, d_vec, f_vec, u, time);
}
計算量は非連結の場合もすべての頂点とすべての枝を 1 回ずつ探索するため、O(n + \sum_{u=1}^n k_u) です。この問題の場合、枝の本数の上限は n^2 となるため、計算量は O(n^2) = 10^4 程度で実行時間制限に違反せずに解答できます。
25. AOJ 1160 – 島はいくつある？
陸を点、縦横斜めに隣接する陸と陸の間に辺があると考えるとグラフの連結成分の個数を答える問題になります。
ある点から深さ優先探索を開始すると、始点と同じ連結成分に属する点の探索を終えた後、深さ優先探索は終了します。この時、探索できていない点は始点とは異なる連結成分に属します。つまり、すべての点を探索するまでの深さ優先探索の始点の数、あるいは深さ優先探索の実行回数が連結成分の個数 (島の数) になります。
隣接する陸の探索方法ですが、下記のように隣接した座標と元の座標の差分の配列 dx と dy を用意すると、実装が楽になります。
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
二次元配列 c_grid を地図、x, y を元の陸の座標として、下記のように隣接した座標が陸か海かを探索できます。
for (int i = 0; i < 8; ++i) {
// 隣接する点 x2, y2 を列挙
int x2 = x + dx[i];
int y2 = y + dx[i];
if (x2 < 0 || h <= x2 || y2 < 0 || w <= y2) // 地図からはみ出る場合
continue;
if (c_grid[x2][y2] == 1) // 隣接する点 x2, y2 に陸がである場合
}
上記を元に深さ優先探索の関数を作成し、その関数を main 関数から何回実行したかを数えると答えが得られます。計算量は O(hw) = 10^4 程度です。
26. AtCoder Beginner Contest 138 D – Ki
Q 回の操作を忠実に実行すると 1 度の木の探索で \Omega(N) かかるため、計算量は \Omega(NQ) = 10^{10} となり、実行時間制限に違反しそうです。
この問題の簡単な類題として、以下のような問題を考えます。
1 から N までの番号がついた N 個の箱が番号の順に左から一列に並んでいます。各箱にはカウンターが設置されており、はじめすべての箱のカウンターの値は 0 です。
これから、以下のような Q 回の操作が行われます。
- 操作 j (1 \leq j \leq Q): 箱 p_j 及び、箱 p_j より右側のすべての箱のカウンターの値に x_j を足す。
すべての操作のあとの各箱のカウンターの値を求めてください。
この類題は累積和を使うと O(Q + N) で求解できます。具体的には下記の処理で求解できます。
- 操作 j に対し、箱 p_j のカウンターに x_j を足します。(計算量 O(Q))
- 箱 i = 1, \dots, N に対し、箱 i + 1 のカウンターに箱 i のカウンターの値を足します。(計算量 O(N))
箱の列を、箱を頂点、箱 1 を根、箱の隣接を辺とする木とみなすと、上記の解法は元の問題の木が特殊な場合の解法となることがわかります。類題の箱 i と箱 i + 1 の関係は元の問題の親と子の関係であるため、下記のように処理を変更すると元の問題の解法になります。
- 操作 j に対し、頂点 p_j のカウンターに x_j を足します。
- 親のカウンターの値から決まる順序で、各頂点 i に対し、頂点 i のカウンターに親のカウンターの値を足します。
2 の「親のカウンターの値から決まる順序」は深さ優先探索で処理すれば実現できます。
計算量は処理 1 で O(Q), 処理 2 で木の深さ優先探索を一度行うため O(N), あわせて O(N + Q) = 10^6 程度です。
27. JOI 2009 予選 4 – 薄氷渡り
始点を決めて深さ優先探索をして、移動できる区画数の最大値を求めます。
1 回しか訪問しない深さ優先探索と異なる点は区画ごとに探索が終わったら (深さ優先探索の帰りがけに)、薄氷を復元する点です。復元を行わないと、元々は薄氷があったが前の探索で割ってしまい薄氷が無くなった区画ができるため、正しい区画数より少なく数えてしまいます。
探索を行う再帰関数を下記のようにすると移動できる区画の最大値が計算できます。
- 関数が呼び出される前に移動した区画の枚数を引数にします。
- 引数の座標に移動し、薄氷を割り、現在の広場の状態を更新します。
- 引数の区画数と現在の区画 (1 枚) と現在の広場の状態で移動できる区画数の最大値の和を返します。
- 最大値を求めるために左右上下の区画に移動して関数を再帰します。
薄氷の復元を行うと計算量が深さ優先探索に比べて増えますが、問題文には下記の記述があります。
与えられる入力データでは， 移動方法は 20 万通りを超えない．
深さ優先探索的に移動方法を列挙した場合、1 つの移動方法から別の移動方法を列挙するまでにかかる最悪計算量は O(mn) ですが、ならし計算量は O(1) になります。最後に枝分かれした薄氷から x 枚割って周りに薄氷が無くなった場合、次の移動方法を列挙するまでに x 回、薄氷を復元する必要があるため、計算量が O(x) になります。ただし、薄氷を x 回割るまでに x 通りの移動方法を列挙しています。そのため、ならすと O((x \cdot 1 + x) / (x + 1)) = O(1) の計算量で 1 つの移動方法から別の移動方法を列挙します。
以上から 10^6 程度の計算量になり、実行時間制限を満たして解答できます。
