深さ優先探索のテンプレート
引数の頂点変数について、大雑把な方針としては
- 頂点インデックスが不要なとき→頂点の値 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
ソースコード
- 完全グラフの完全マッチング問題
- bitsetを使うと定数倍高速化できる
- 陽にグラフを持たないけど頂点番号しか使わないので引数には vi を渡す
ll ans=0; using bit=bitset<17>; auto dfs=[&](auto self, bit vis, ll vi, ll sum)->void { if(vi>=N) return; rep(vj,vi+1,N+1) { if(vis[vj]) continue; umax(ans,sum+D[vi][vj]); ll nvi=vi+1; repf(,vis[nvi]||nvi==vj,nvi++); self(self,vis|bit(lpow(2,vj))|bit(lpow(2,nvi)),nvi,sum+D[vi][vj]); } };
ABC196D - Hanjo
ソースコード
ll ans=0; veb mat; make2d(mat,H,W); auto dfs=[&](auto self, cll a, cll b, cll yi, cll xi)->void { if(orange(mat,yi,xi)) { if(a==0&&b==0) ans++; return; } // j=0 横畳 j=1 縦畳 j=2 半畳 j=3 不使用 rep(j,0,4) { if(j==0) { if(a==0) continue; if(orange(mat,yi,xi)||orange(mat,yi,xi+1)) continue; if(mat[yi][xi]||mat[yi][xi+1]) continue; ll nyi=yi; ll nxi=xi+2; if(orange(mat,nyi,nxi)) nyi++,nxi=0; mat[yi][xi]=mat[yi][xi+1]=1; self(self,a-1,b,nyi,nxi); mat[yi][xi]=mat[yi][xi+1]=0; } else if(j==1) { if(a==0) continue; if(orange(mat,yi,xi)||orange(mat,yi+1,xi)) continue; if(mat[yi][xi]||mat[yi+1][xi]) continue; ll nyi=yi; ll nxi=xi+1; if(orange(mat,nyi,nxi)) nyi++,nxi=0; mat[yi][xi]=mat[yi+1][xi]=1; self(self,a-1,b,nyi,nxi); mat[yi][xi]=mat[yi+1][xi]=0; } else if(j==2) { if(b==0) continue; if(orange(mat,yi,xi)) continue; if(mat[yi][xi]) continue; ll nyi=yi; ll nxi=xi+1; if(orange(mat,nyi,nxi)) nyi++,nxi=0; mat[yi][xi]=1; self(self,a,b-1,nyi,nxi); mat[yi][xi]=0; } else { ll nyi=yi; ll nxi=xi+1; if(orange(mat,nyi,nxi)) nyi++,nxi=0; self(self,a,b,nyi,nxi); } } };
