全探索

問題へのリンク

問題概要

桁ごとに見た時、隣り合う数字の差の絶対値が 1 以下になる数を考える。小さいほうから K 番目の数を求めよ

制約\(1 \leq K \leq 10^5\)
考え方

制約が結構重要で ...

Nが自然数の2乗で表現できるとき、平方数と言います。

平方数の例4 (= 2×2)
9 (= 3×3)
16 (= 4×4)
25 (= 5×5)
アルゴリズム

以下の方法以外にも色々な求め方 ...

N 個の要素の組み合わせを計算する際、N/2 ずつの2グループに分けてそれぞれを全列挙し、組み合わせ方を高速に求めるという工夫を「半分全列挙」と言います。

選択した数列の合計値を半分全列挙で探索する場合（\(2^4\)ずつに分け ...

問題

平面上でN個の座標が与えられる。全ての点を１回ずつ通るような動き方は\(N!\)通りあるが、これらの総移動距離の平均を求めよ。

元の問題: C – Average Length

解き方

二通りの方 ...

深さ優先探索とは、全探索アルゴリズムの一種です。グラフや、グラフと同一視できるものを探索する際に良く使われます。

幅優先探索(BFS)と似ていますが、深さ優先探索は末端に到達するまで「深く」探索してから、他のノードの探索を ...

ループによる全探索とは

特定の条件を満たすようなものを発見する方法を探索アルゴリズムと言います。全探索は全ての場合を確認して、条件を満たすものが存在するかを判定します。

全探索アルゴリズムの中でもループを使ったものは基本とな ...