技術スポンサードリンクこんにちは!@bluesky177896です。以前の記事で紹介した通り、自分は競技プログラミングを提供するサイトの一つである、AtCorderに登録しています。そこで頻出するアルゴリズムの一つである、「全探索」について今回はまとめてみました。分かりやすく解説していきます。まとめ全探索とは全探索という漢字で察した人もいるかと思いますが、「全てのパターンを探索してみる」アルゴリズムとなります。Wikipediaでは「力任せ探索」という項目名になっています。以下のような設問があったとします。あなたは、500円玉を300枚、100円玉を200枚、50円玉を100枚持っています。これらの硬貨の中から何枚かを選び、合計金額をちょうど15000円にする方法は何通りありますか。参考:AtCorderで全探索を中心にした問題が出ている回「abc087」(B問題)こうなったとき、色々考え方はあると思います。全探索で考えるとどうなるかというと、以下のようなグラフを作って埋めていくようなイメージになります。私たちがやるのは競技プログラミング!実際にコードに落としこんで考えていきましょう。行い、貨幣の種類分forのネストを深くすればOKです。{count++;}}}}System.out.println(count);}}この通り、比較的短いコードで簡単にかけてしまいました。(TLE)」という判定があります。これは、英語の通り「時間切れ」で、あまり処理が長いと答えがあっていても回答を受け付けてもらえません。目安としては、int型をforで処理する回数が10^12程度にならなければ問題ないかと思います。(AtCorderで言うと、~一部のC問題までなら全探索でTLEが出ることはまずないと思います。C++などはもう少し無理できるかもしれません。上記の問題は、非常に単純なループで作成しました。下の方に書いたように、全探索は制限等によっては処理時間が非常に長くなるという欠点があります。した応用をして時間を短縮出来るようになると嬉しいし、C問題以降を解いていくための練習にもなります。上の例でみていくと、実は最後の50円のループは回す必要がありません。いうのも、500円玉、100円玉の枚数が決定した時点で、ちょうどにしたい金額にするために必要な50円玉の枚数を私たちは簡単に求めることが出来るからです。ループの途中で500円玉が10枚、100円玉が10枚のパターンが来るとします。この時点で7000円で、残り必要な金額は8000円になります。必要な50円玉の枚数は?8000/50で160枚です。50で割り切れて、かつ制限枚数以内に収まっています。これより上にもこれより下の枚数にもできないので、この時点で50円玉の他の枚数で合計がどうなるかは計算する必要はありません。この時点でマッチしたパターン数を一つ増やして、次のループ処理に移ってOKとなります。これをコードに落とし込むと、以下の様になります。金額から引いた時にマイナスになり、計算がおかしくなるからです。この他にも、様々な方法で回答をより高速に出せるようにしている方が沢山います。自分で見つけられるようになるととても楽しいです。「ちょっとした工夫」をすることで解くことが可能です。(自分が初めて解説無しに解けたC問題で、恐らくそんなに難易度が高くないと思うので是非C難しい層の方はチャレンジしてみてください!)まとめというわけで、文系でも理系でもない人間が全探索についてまとめてみました。粗はありますが、究極的には「AC」が出ればいいのです。このくらいのふんわりした理解でも全探索問題ならCでもコンスタントにACを出せるので、全探索を知らない方の参考や励みになればと思います。必要なアルゴリズムやテクニックが分かりやすく解説されている本です。少なくともJavaユーザーの私はなんとか解読出来るレベルなので、かなり読みやすく書かれています。(もしくは、これを機にC++デビューをしても良いかもしれません。少なくともJavaと違って記述量が短く済むので、コードを書く時間で圧倒的に有利だと思います。某配送システム白猫プロジェクトのアイシャが大好きなエンジニアの卵。Java/Shell/C++/HTML/Sass/rustかgoやりたい。コメントをキャンセルメールアドレスが公開されることはありません。コメントデータの処理方法の詳細はこちらをご覧ください。WordPress.。