はじめに
こんにちは，光岡です．
最近少しだけですが，競技プログラミングを始めました． コンテストに参加しているわけではなく，現状だとコーディングテスト対策がメインになっていますが，慣れてきたら参戦してみたいです．
まずは基本の全探索から始めてみるか〜と思い，AtCoderの問題を解いているのですが，単純にfor文を回すと時間切れ（TLE: Time Limit Exceeded）になる問題あたりから，すんなり正解できなくなってきました．．
そこで，探索系の問題が出たときの自分用の解法のテンプレ集を作ってみました！
解き始めに確認すること
実行回数を見積もる
問題を解き始める際に最初に確認することは， ズバリ，単純にfor文を回すだけでOKな問題か確認することです！
AtCoderでは，処理の制限時間は1~2秒，1秒あたり108回程度の計算が可能と言われています．
つまり，単純なfor文を回した際に，2 * 108回を超えないか，実行時間を見積もることが大事です．
自分は最初なんとなくコードを書き始めてしまっていたので，コードを提出してみたらTLE→修正のサイクルでやってしまってました．．
工夫
単純にfor文を回すとTLEになってしまう．．．そんな時は，問題文を注意深く読み，処理が減らせないか考えます． そのために，全探索問題に出会った時に，使える可能性のあるテクニックをまとめてみます．
for文で考慮すべき上限を確かめる
問題文
正整数 X が与えられます。 X 以下の最大のべき乗数を求めてください。 ただし、べき乗数とは、ある 1 以上の整数 b と 2 以上の整数 p を使って bpとかける整数のことを指すこととします。
制約
1 ≤ X ≤ 1000
X は整数
この問題の制約では，べき乗数がいくつまでかの記載はありませんが，1以上の整数（1は何乗しても1のため，2で考える）と記載あるため，2x が1000を超える時が，べき乗数pの最大値になります．
つまり，210 = 1024 より，2 ≤ X ≤ 10を考慮して，for文を回すと余計な処理を行わずに，実装することができます．
条件から残りの変数を導き出す
問題文
2 つの整数 K,S が与えられます。
3 つの変数 X,Y,Z があり、0≦X,Y,Z≦K を満たす整数の値を取ります。
X+Y+Z=S を満たす X,Y,Z への値の割り当ては何通りありますか。
制約
2≦K≦2500
0≦S≦3K
K,S は整数である。
何も考えずに解き始めると，for文でX, Y, Zの3回分回そうとしてしまいがちですが，
X+Y+Z=Sより，for文2回で，X, Yを指定した段階で，Z=S-X-Yにより，for文2回のままZを導き出すことができます．
実行時間の見積もりも，for文3回だと，
2500^3 = 2.5^3 * 10^9 > 2 * 10^8
となりTLEしますが，for文2回だと，
2.5^2 * 10^6 < 2 * 10^8
となり，TLEしなくなります！
bit全探索
一回の操作が2通り（スイッチのON/OFF，硬貨が表/裏，．．．）の時，つまり*2N通りを全探索する際は，二進数を使います！
使える問題
複数ある商品（最大 2020 個程度）それぞれについて『買う』『買わない』とか、複数ある整数をそれぞれについて『選ぶ』『選ばない』といった、2 種類の選択肢が複数ある問題
bit全探索でやること
そのタイプの問題で、『ありえる選択肢の組み合わせ方を全てもれなく列挙』して、『一つ一つの組み合わせに対して計算や判定を行う』ことで、答えを見つけるアルゴリズム
こわくないbit全探索1 入門編: bit全探索ってなに？【競プロ解説】 - Qiita
bit全探索が主題された時のテンプレとしては下記の記事がとてもわかりやすく，参考にしています．論理積&, ビットシフトに関しての記載はここでは割愛しますが，気になったらぜひ確認してみてください！
参考コード
for i in range(2**N): for j in range(N): if (i>>j) & 1:
bit全探索の注意点
組み合わせは2N通り．指数関数的に増えるため，実装時間の見積もりに注意が必要です．
Python3 → PyPy3 で提出
これはPythonを利用している方限定ですが，言語指定をPyPyにするだけで処理速度が速くなり，フィボナッチ数列の出力では約2.4倍速いそうです．ギリギリTLEしていたら，正解（AC: Accepted）になる可能性あります！
PyPyの説明については下記記事で確認してみてください！
おわりに
まだまだ色々な全探索の解法があり，今回取り上げたのは一部ですが，今後もまとめたいものを追記していきたいと思います！
