7K12 blog

猫でも分かる何か

深さ優先探索 auto dfs

深さ優先探索のテンプレート

引数の頂点変数について、大雑把な方針としては

  • 頂点インデックスが不要なとき→頂点の値 vx
  • 陽にグラフを持つとき→頂点インデックス vi
  • 複雑な状態を持つとき→必要な状態全部

状態のオーバーヘッドが大きいときは参照渡しにして保存処理と復元処理を追加する
陽にグラフ構造を持つ深さ優先探索のときは頂点を記録するcnt配列を用意して無限ループを防ぐ

auto dfs=[&](auto self, 頂点)->void {
	if(再帰の終了条件) return;
	(必要ならば)cnt[vi]++;
	遷移する前の計算
	for(辺の本数だけ繰り返す) {
		if(遷移しない条件) continue;
		(必要ならば)状態の保存処理
		遷移するための計算
		self(self,次の頂点);
		(必要ならば)状態の復元処理
	}
	全ての辺から戻ってきたときにする計算
};


メモ化する深さ優先探索のテンプレート

ABC340C - Divide and Divide
ソースコード
  • map を参照することで計算量を削減できる
  • 辺の本数は計算済かどうかで異なるので for(;;) と if() break を使って工夫した
  • 頂点の計算は全ての子頂点から帰ってきたときにするので for の後に書く
mall memo; memo[1]=0;
auto dfs=[&](auto self, ll vx)->void {
	if(vx==1) return;
	for(;;) {
		if(lfind(memo,ldiv(vx,2,true))&&lfind(memo,ldiv(vx,2,false))) break;
		ll nvx=0;
		if(!lfind(memo,ldiv(vx,2,true))) nvx=ldiv(vx,2,true);
		else if(!lfind(memo,ldiv(vx,2,false))) nvx=ldiv(vx,2,false);
		self(self,nvx);
	}
	memo[vx]=vx+memo[ldiv(vx,2,true)]+memo[ldiv(vx,2,false)];
};
  • ただし、単純な末尾再帰の場合はコード量の少ないアドホックな書き方もある
mall memo; memo[1]=0;
auto dfs=[&](auto self, ll vx)->ll {
	if(lfind(memo,vx)) return memo[vx];
	memo[vx]=vx+self(self,ldiv(vx,2,true))+self(self,ldiv(vx,2,false));
	return memo[vx];
};
  • OEIS を使えば1行で済む
out(N*llog(2,4*N,false)-lpow(2,(llog(2,2*N,false))));

陽にグラフを持つ深さ優先探索のテンプレート

ABC138D - Ki
ソースコード
  • 頂点に遷移した回数を記録するcnt配列を用意して無限ループを防ぐ
  • 計算に頂点インデックス vi と次の頂点インデックス nvi が必要なので、遷移直前に ans[e.nvi] を更新した
vel add(N),ans(N),cnt(N);
repe(e,px) add[e.a]+=e.b;
ans[0]=add[0];
auto dfs=[&](auto self, ll vi)->void {
	cnt[vi]++;
	for(auto& e:g[vi]) {
		if(cnt[e.nvi]) continue;
		ans[e.nvi]+=ans[vi]+add[e.nvi];
		self(self,e.nvi);
	}
};

陽にグラフを持たない深さ優先探索のテンプレート

ABC161D - Lunlun Number
ソースコード
  • 陽にグラフを持たないので引数の頂点は vx を渡せば良い
vel ans;
nlb rep(len,1,inf) rep(x,1,10) {
	auto dfs=[&](auto self, ll vx)->void {
		if(lsz(vx)==len) {
			push(ans,vx);
			return;
		}
		rep(d,-1,2) {
			ll nex=vx%10+d;
			if(nex<0||9<nex) continue;
			ll nvx=vx*10+nex;
			self(self,nvx);
		}
	};
	dfs(dfs,x);
	if(lsz(ans)>=K) return;
} nle;

ABC318D - General Weighted Max Matching

ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

ll ans=ll();
struct DS { ll i=ll(); UnSeDeque<ll> sel; ll sum=ll(); };
// https://9871225.hatenablog.com/entry/2023/12/12/080903
auto dfs=[&](auto self, DS& s)->void {
	if(s.sel.size()==N) return; // 再帰の終わり

	rep(j,s.i+1,N+1) {
		// 保存、状態の更新
		if(s.sel.find(j)) continue;
		s.sel.push_back(j),s.sum+=D[s.i][j];
		if(s.sel.size()==N) ans=max(ans,s.sum);
		while(s.sel.find(s.i)) s.i++;
		s.sel.push_back(s.i);
		// 遷移、状態の復元
		self(self,s);
		s.i=s.sel[s.sel.size()-3];
		s.sum-=D[s.sel[s.sel.size()-3]][s.sel[s.sel.size()-2]],s.sel.pop_back();
		s.sel.pop_back();
	}
};

ABC196D - Hanjo

ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vvb=vector<vector<bitset<1>>>;

ll ans=0;
struct DS { ll a=ll(); ll b=ll(); ll iy=ll(); ll ix=ll(); vvb check; };
auto dfs=[&](auto self, DS& s)->void {
	if(s.a==0&&s.b==0) ans++;
	if(s.iy<0||H<=s.iy||s.ix<0||W<=s.ix) return; // 再帰の終わり

	// j=0 縦畳 j=1 横畳 j=2 半畳
	auto nyx=[&](ll& y, ll& x) { x++; if(x==W) x=0,y++; }; 
	for(ll j=0;j<3;j++) {
		// 保存、状態の更新
		if((j<=1&&s.a==0)||(j==2&&s.b==0)) continue;
		if(j==0&&((s.iy<0||H<=s.iy||s.ix<0||W<=s.ix)||s.check[s.iy+1][s.ix]==true)) continue;
		if(j==1&&((s.iy<0||H<=s.iy||s.ix<0||W<=s.ix)||s.check[s.iy][s.ix+1]==true)) continue;
		DS rec=s;
		if(j==0) s.check[s.iy][s.ix]=s.check[s.iy+1][s.ix]=true,s.a--;
		if(j==1) s.check[s.iy][s.ix]=s.check[s.iy][s.ix+1]=true,s.a--;
		if(j==2) s.check[s.iy][s.ix]=true,s.b--;
		while(!(s.iy<0||H<=s.iy||s.ix<0||W<=s.ix)&&s.check[s.iy][s.ix]==true) nyx(s.iy,s.ix);
		// 遷移、状態の復元
		self(self,s);
		s=rec;
	}
};