next_combination を使った！ 普通に STL の next_permutation() でもできる。 問題へのリンク 問題概要 頂点数 、辺数 の連結な重み付き無向グラフが与えられる。 このグラフの全域木をすべて考えたときの、全域木に含まれる辺の重みの総和を で割ったあま…

面白い最適化問題！ 問題へのリンク 問題概要 二次元平面上で、原点からの距離が であるような 点の凸包の面積として考えられる最大値を求めよ。 制約 考えたこと 凸包というところが面倒だが、要は 本のうちの何本かを選んで それを適切な順序に並び替えた…

ゲーム探索 + bit DP。やや実装重たい。 問題へのリンク 問題概要 先手と後手が交互に のグリッドの各マス目に o や x を書いていく。先手は o を書き、後手は x を書く。 書き終わったとき、次のように得点を計算する および に対して、 マス とマス が同じ…

「並び替え方」の全探索は、C++ なら next_permutation()、Python3 なら itertools.permutations() が使える！ 問題へのリンク 問題概要 個の長さ の文字列 が与えられる。 これらを並び替えて得られる文字列 であって、 「 と が 1 文字違いである」() とい…

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

整数 を 8 で割ったあまりは、 の下三桁を 8 で割ったあまりに等しい！ 問題へのリンク 問題概要 整数 が長さ の文字列として与えられる ( は '1'〜'9' のみで構成される)。 の各文字を並び替えてできる整数の中に、8 の倍数となるものが存在するかどうかを…

next_permutation の練習になりそう。DFS でも。 問題へのリンク 問題概要 の順列 が与えられます。 が の順列のうち辞書順で何番目か が の順列のうち辞書順で何番目か を求め、それらの差を答えよ。 制約 考えたこと 制約が小さいので、 通りの順列をすべ…

グラフの探索を頑張る問題。現代の AtCoder であまり見ないけど、教育的な全探索問題！！！ 問題へのリンク 問題概要 頂点数 、辺数 の無向グラフが与えられる。このグラフ上で頂点 1 から出発するハミルトンパスが何本あるかを数え上げよ。 なおハミルトン…

Floyd-Warshall で前処理してどうのこうのする問題。特に ICPC 系などでよくある！ 問題へのリンク 問題概要 頂点 辺の重み付き無向グラフが与えられる。 このグラフ上で 個のチェックポイントをなす頂点集合が指定されている。好きなチェックポイントからス…