n重ループを書きたくなる再帰全探索を巻き戻しテクを使って解く
先日のABC165-Cが難しかったようなので、おすすめの実装法を紹介してみます。
この問題に限らず、愚直にやるとn重ループを書きたくなってしまう全探索問題全般に適用できるのでオススメです。
問題リンク:
atcoder.jp
とりあえずコードを乗せます。
#include <iostream> #include <vector> #include <iterator> using namespace std; int n, m, q; int a[50], b[50], c[50], d[50]; int dfs(vector<int> &v) { if (v.size() == n) { // 数を選び終わったのでシミュレート int sum = 0; for (int i = 0; i < q; i++) { if (v[b[i]] - v[a[i]] == c[i]) sum += d[i]; } return sum; } int last = (v.empty() ? 1 : v.back()); int Max = 0; for (int i = last; i <= m; i++) { // 追加 -> 先を探索 -> 削除 v.push_back(i); Max = max(Max, dfs(v)); v.pop_back(); } return Max; } int main() { cin >> n >> m >> q; for (int i = 0; i < q; i++) { cin >> a[i] >> b[i] >> c[i] >> d[i]; a[i]--, b[i]--; } vector<int> v; cout << dfs(v) << endl; return 0; }
関数dfsは「現在選んだ数が順にv1, v2, ..., viであるとき、それ以降の要素をうまく定めたときの題意の値の最大値」を取得する関数です。
引数にvectorの参照を取ることで、どの階層においても同じvectorを参照できます。別に参照じゃなくてもいい場合もありますが、値のコピーが行われるため遅いです。
vectorのサイズがnのときは数をn個選び終わったということなので、問題文の値をシミュレートした結果を返します。
それ以外のとき、vectorの末尾の要素(vectorが空の場合は1)をlastとすると、次に選べる数はlast, last+1, ..., Mとなります。
追加する要素をiとしたとき、
・vectorの末尾にiを追加する。
・要素を追加した新たなvectorに対してdfsを呼ぶ。返値の最大値を更新する。
・vectorの末尾を削除する。
という操作をひとまとめにして行うことで、各ループの開始時と終了時にvectorの値が変化しないようにしつつ先の探索を行うことが出来ます。
イメージとしては、数を追加してその先を全て調べた後、Undo操作を行って追加をなかったことにする感じ。
この考え方は同じような問題全般に適用できます。
抽象的に言い換えると、
・あるコンテナ(再帰関数全体において共通)に変更を加える。
・関数を再帰的に呼び、先を探索する。
・変更を打ち消す操作を行い、変更をなかったことにする。
となります。このとき変更および変更のUndo操作が高速に動作する必要があります。変更/Undoの計算量が重い場合は別の方法を検討しましょう。(DFSが想定解の問題ではあんまりなさそう?)
類題
パナコン2020-D String Equivalence
問題リンク:
atcoder.jp
こちらもかなり難しいと言われていた気がします。
文字列c1c2c3...ciに新たな文字を追加する際に追加できるのは、今まで使った文字、及び使用済み文字の(アルファベット順で)最大のものより1だけ大きい文字に限ります。
現在の文字列とその文字列内の最大の文字を引数に取ることで上手くいきます。
提出コード:
Submission #12677860 - Panasonic Programming Contest 2020
ABC114-C 755
問題リンク:
atcoder.jp
こちらも同様のDFS全探索題です。ただし今回は長さが特に決まっているわけではないので注意です。
提出コード:
Submission #12678082 - AtCoder Beginner Contest 114
(あまりきれいではないですが、頭を使わずに書けるのが強みです。)
ABC165-F LIS on Tree
問題リンク:
atcoder.jp
同コンテストで出題された、木上の狭義最長増加部分列(LIS)を求める問題。
全探索ではないですが、vectorの扱い方が先程の問題と同じなので紹介しておきます。
LISについてはこの記事が詳しいです。
qiita.com
先程と同様に、dpテーブルを更新、先を探索、更新を取り消すとすればよいです。
dpテーブルを更新した際にその頂点までのLISも求めておきましょう。
提出コード:
Submission #12677558 - AtCoder Beginner Contest 165