1から蓄えるAtCoder備忘録 -1:全探索
自己紹介
初投稿なので軽く自己紹介的なものをここに載せておきます！
初めまして、hayato95と申します。
大学生からPCに興味を持ってwindowsでなんか色々してます！
ゲーム開発、アプリ開発、競プロ、テニス、いっぱい興味持ってます！
すごい初心者なので拙い部分も数多くあるかと思いますが、ご容赦いただけますと幸いですm(__)m
このシリーズについて
AtCoderの学習記録を備忘録として残していこうかなと思っております！
何かしら１つの言語の文法をある程度学んでいれば、内容的には十分問題ないかと！
僕の使っている環境は以下の通りです：
- 使用言語：C++
- 環境：Windows 11
もしC++を触った事なくても、AtCoder公式の入門教材APG4bで一通り学べます👇
APG4b - AtCoder Programming Guide for beginners
実装には以下の知識があるとスムーズです。
- for文・if文（条件分岐と繰り返し）
- 配列・リストの扱い
早速：全探索って何？
おそらく一番最初に学習するであろうアルゴリズムがおそらく全探索かなと。
名前の通り、全部のパターンを探索して、答えを確定させる(脳筋)手法。
シンプルな考え方ですが、条件さえ合えば確実に正解にたどり着ける優等生。
いつ使える？判断基準
計算量（処理回数）が1億回以内に収まるかどうかで判断。
(大体家庭用コンピュータの処理速度が1秒間に10億回程度)
判断の手順
- 変数の最大値を問題文から確認する
- ループ回数を計算する（最大値^ループの深さ）
- 1億回以内 → 全探索OK
- 1億回超え → 別のアルゴリズムへ
なぜ1億回が基準なのか
コンピュータの処理速度から逆算できます。
- CPUの理論値：約10^9回/秒（GHz級）
- ただし実際のコードではメモリアクセス・条件分岐・関数呼び出しのオーバーヘッドが重なる
- 実効速度は理論値の約1/10
CPU理論値 10^9 ÷ 実装コスト（約10倍）= 実用目安 10^8
具体例
3重ループの場合
| 各変数の通り数 | ループ回数 | 判定 |
|---|---|---|
| 30通り | 30^3 = 27,000回 | ✅ OK |
| 500通り | 500^3 ≈ 1.25×10^8回 | ✅ ギリOK |
| 1,000通り | 1,000^3 = 10^9回 | ❌ TLE（時間超過） |
例題で試してみようのコーナー
概念が掴めたら実際の問題で確認してみましょう！
👇 全探索で解けるB問題
ABC129 B - Balance
ヒント：Tを1からN-1まで全部試して、差の絶対値が最小になるものを探してみると...?
まとめ
- 全探索が使えるかどうかは「変数の最大値でループ回数を見積もって1億回以内か」で判断する
- これを超えたら二分探索やDP（動的計画法）など計算量を削る手法を検討するらしい
次回以降も(気が向いたら)投稿してみようと思います！
最後まで付き合っていただいた方、本当にありがとうございましたm(__)m
次回：
1から蓄えるAtCoder備忘録 -2: 重複なしで値を数える（map／連想配列）
参考文献
- 競技プログラミングの鉄則（著：米田優峻）
- APG4b - AtCoder Programming Guide for beginners
- ABC129 B - Balance