けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

再帰関数を用いた全探索

競プロ典型 90 問 002 - Encyclopedia of Parentheses(★3)

整合したカッコ列を bit 全探索する問題!!! 問題へのリンク editorial へのリンク 類題とか drken1215.hatenablog.com drken1215.hatenablog.com 問題概要 長さ の「整合したカッコ列」を辞書順にすべて列挙せよ。 整合したカッコ列の意味については、問…

AtCoder ABC 183 C - Travel (灰色, 300 点)

C++ なら next_permutation() を使うことで 通りの全探索ができる! 問題へのリンク 問題概要 個の都市 がある。都市 と都市 とは距離が だけ離れている。 都市 から出発して各都市をちょうど一度ずつ訪問して都市 に戻ってくる方法のうち、その移動距離の総…

よくやる再帰関数の書き方 〜 n 重 for 文を機械的に 〜

時は 2020 年 5 月 3 日。 ここ最近、AtCoder では、「再帰関数を用いた DFS な全探索」というタイプの問題が激増しています!!! AtCoder ABC 165 C - Many Requirements (昨日のやつ) AtCoder ABC 114 C - 755 AtCoder ABC 119 C - Synthetic Kadomatsu A…

AtCoder ABC 161 D - Lunlun Number (緑色, 400 点)

この手の DFS、一時期全然見なかったけど、最近復活してきた! 問題へのリンク 問題概要 1 以上の整数であって、隣り合う桁の値の絶対値が 1 以下であるような数をルンルン数とよぶ。 番目に小さいルンルン数を求めよ。 制約 考えたこと さて、「 番目に小さ…

bit 全探索を「再帰関数」で書く 2 つの流儀

0. はじめに bit 全探索は、世の中で「AtCoder 温室育ちだと弱い」と言われるタイプの問題の代表かもしれません。何も考えずに思考停止して全探索すればよいのですが、ちょっと実装が重たい傾向にあって、書き切るのが大変という感じです。difficulty を見て…