全探索:再帰関数
こういう探索系はみんな苦手とするイメージだったけど、結構 Difficulty 低いのね。 問題へのリンク 問題概要 グリッドで、各マスは「空き」または「壁」である。 ある空きマスを出発し、上下左右に隣接するマスへの移動を 回行う方法であって、障害物のある…
再帰関数を使った全探索の練習！ こういうのは本当に練習になる。 問題へのリンク 問題概要 各マスが 0 または 1 であるような の二次元グリッド が与えられる。 グリッド上の各マスを渡り歩いていく移動経路のうち、次の条件を満たすものを考える。 1 回の…
全探索の基礎になるような再帰関数の使い方！ 問題へのリンク 問題概要 以下の条件を満たす長さ の整数列を辞書順で小さい方から順に出力せよ。 番目の要素は 以上 以下 総和が の倍数 制約 考えたこと このように、長さ のさまざまな数列を生成する方法につ…
next_combination を使った！ 普通に STL の next_permutation() でもできる。 問題へのリンク 問題概要 頂点数 、辺数 の連結な重み付き無向グラフが与えられる。 このグラフの全域木をすべて考えたときの、全域木に含まれる辺の重みの総和を で割ったあま…
最近、実装重たい全探索問題多いね！ 問題へのリンク 問題概要 下図のようなポリオミノが 3 個与えられる。いずれも 4 × 4 グリッドにおさまるサイズであり、入力は 4 × 4 グリッドで与えられる。文字 '#' に対応する部分が与えられるポリオミノに対応する。…
久しぶりの、再帰関数を書きたくなるタイプの全探索！ 問題へのリンク 問題概要 各桁の数値が狭義単調減少になっている数を 321-like 数と呼ぶ。 番目の 321-like 数を求めよ。 制約 321-like 数の個数 解法 (1)：異常 10 重 for 文 この解法は本当に根性で…
再帰関数を使った全探索が書けるかどうかが試される！ 問題へのリンク 問題概要 人のスポーツ選手を 個のグループに分けたい。 ただし、仲の悪いスポーツ選手の組が 組ある。任意の に対して、選手 と選手 を同じグループに属させてはならない。 この制約を…
「並び替え方」の全探索は、C++ なら next_permutation()、Python3 なら itertools.permutations() が使える！ 問題へのリンク 問題概要 個の長さ の文字列 が与えられる。 これらを並び替えて得られる文字列 であって、 「 と が 1 文字違いである」() とい…
ビット全探索もついに茶色 diff ですね！ 問題へのリンク 予備知識 ビット全探索の知識があると解きやすいです！ 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 を見て…
bit 全探索 問題へのリンク 問題概要 個のスイッチがある。スイッチによって 個の電球が点いたり消えたりする。 電球 は 個のスイッチに繋がっており、スイッチ のうち on になっているスイッチの個数を 2 で割った余りが に等しい時に点灯します。 全ての電…
現代の AtCoder では少ない、再帰関数を用いると良い感じに書ける全探索問題。 すごく教育的な問題！！！！！ 問題へのリンク 問題概要 10 進法表記で各桁の値が 7 と 5 と 3 のみで、かつ 7, 5, 3 がすべて一度以上は登場するような数を「753 数」と呼ぶこ…
最近の AtCoder は ABC でも考察重視傾向が強くて、こういうのが見落とされがちかもしれない。 でも ABC を競プロ入門コンテンツと見たとき、この種の出題がもっと増えると良さそう！！！！！ 大事なことを再認識させてくれる感じ。 問題へのリンク 問題概要…
すごく教育的な「bit 全探索 + Greedy」！！！ 問題へのリンク 問題概要 100 点問題, 200 点問題, 300 点問題, ..., 100× 点問題がそれぞれ 問ずつある。 今、精進して合計で 点以上獲得したい。ただし、100× 点問題を 問すべて解いた場合にはボーナスとして…
整合したカッコ列を bit 全探索する問題！！！ 問題へのリンク editorial へのリンク 類題とか drken1215.hatenablog.com 問題概要 長さ の「整合したカッコ列」を辞書順にすべて列挙せよ。 整合したカッコ列の意味については、問題ページにて。 制約 考えた…
