再帰関数を用いた全探索
整合したカッコ列を bit 全探索する問題！！！ 問題へのリンク editorial へのリンク 類題とか drken1215.hatenablog.com drken1215.hatenablog.com 問題概要 長さ の「整合したカッコ列」を辞書順にすべて列挙せよ。 整合したカッコ列の意味については、問…
C++ なら next_permutation() を使うことで 通りの全探索ができる！ 問題へのリンク 問題概要 個の都市 がある。都市 と都市 とは距離が だけ離れている。 都市 から出発して各都市をちょうど一度ずつ訪問して都市 に戻ってくる方法のうち、その移動距離の総…
時は 2020 年 5 月 3 日。 ここ最近、AtCoder では、「再帰関数を用いた DFS な全探索」というタイプの問題が激増しています！！！ AtCoder ABC 165 C - Many Requirements (昨日のやつ) AtCoder ABC 114 C - 755 AtCoder ABC 119 C - Synthetic Kadomatsu A…
この手の DFS、一時期全然見なかったけど、最近復活してきた！ 問題へのリンク 問題概要 1 以上の整数であって、隣り合う桁の値の絶対値が 1 以下であるような数をルンルン数とよぶ。 番目に小さいルンルン数を求めよ。 制約 考えたこと さて、「 番目に小さ…
0. はじめに bit 全探索は、世の中で「AtCoder 温室育ちだと弱い」と言われるタイプの問題の代表かもしれません。何も考えずに思考停止して全探索すればよいのですが、ちょっと実装が重たい傾向にあって、書き切るのが大変という感じです。difficulty を見て…
