アルゴリズムについて学びたかったら、先人の知恵に頼るべし
AtCoderを始めてアルゴリズムを今まで知らずに生きてきましたが、アルゴリズムについて知りたくて堪らなくなったので、まずはbit全探索を調べてみました。ちなみに全くアルゴリズムを知らなくてもmax3完(半分は解ける)は出来たので、AtCoderを始めるのにアルゴリズムは必須ではないと思う。知らなくても楽しめます。
しかしアルゴリズムを習ってこそプログラミングの真髄だと思うので、習ってさらに楽しく&解ける問題が増えると嬉しい。
Pythonユーザーならこの2冊が間違いない!
著:岩下 真也, 著:中村 謙弘, 読み手:AtCoder株式会社、高橋 直大
¥3,445 (2024/07/26 00:45時点 | Amazon調べ)
![](https://doctor-koala-blog.com/wp-content/plugins/pochipp/assets/img/pochipp-logo-t1.png)
著:大槻 兼資, 読み手:AtCoder株式会社
¥2,772 (2024/07/26 00:44時点 | Amazon調べ)
![](https://doctor-koala-blog.com/wp-content/plugins/pochipp/assets/img/pochipp-logo-t1.png)
いざ!ググってみる!!
しかし読めども読めども難解。 2進数とかビットとか聞いたことあるけど、改めて全く使いこなせないことを実感。しかしAtCoderの神様は見放してはいなかったようで、下記の素晴らしい記事に出会いました。
Qiita
![](data:image/gif;base64,R0lGODlhAQABAAAAACH5BAEKAAEALAAAAAABAAEAAAICTAEAOw==)
![](https://qiita-user-contents.imgix.net/https%3A%2F%2Fcdn.qiita.com%2Fassets%2Fpublic%2Farticle-ogp-background-412672c5f0600ab9a64263b751f1bc81.png?ixlib=rb-4.0.0&w=1200&mark64=aHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTk3MiZoPTM3OCZ0eHQ9UHl0aG9uJTIwZGUlMjAlRTMlODIlQTIlRTMlODMlQUIlRTMlODIlQjQlRTMlODMlQUElRTMlODIlQkElRTMlODMlQTAlRUYlQkMlODhiaXQlRTUlODUlQTglRTYlOEUlQTIlRTclQjQlQTIlRUYlQkMlODkmdHh0LWFsaWduPWxlZnQlMkN0b3AmdHh0LWNvbG9yPSUyMzIxMjEyMSZ0eHQtZm9udD1IaXJhZ2lubyUyMFNhbnMlMjBXNiZ0eHQtc2l6ZT01NiZzPTI5ZjE2NmU5NjFhYWUzNDVjOTY3ZDU0MDMxMDY1YmEz&mark-x=142&mark-y=57&blend64=aHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZoPTc2Jnc9NzcwJnR4dD0lNDBnb2dvdGVhbG92ZSZ0eHQtY29sb3I9JTIzMjEyMTIxJnR4dC1mb250PUhpcmFnaW5vJTIwU2FucyUyMFc2JnR4dC1zaXplPTM2JnR4dC1hbGlnbj1sZWZ0JTJDdG9wJnM9NTc1ODcyYTM4ZWI1ZGJkY2MxZDc4N2IxZmVmZGQ1Yjg&blend-x=142&blend-y=486&blend-mode=normal&s=cb50f1ffdf89851b4cdf264c4ee558d1)
Python de アルゴリズム(bit全探索) – Qiita
bit全探索とは「n 個の選択肢それぞれに Yes or No の二択があるが、その部分集合(選択できるパターン)の全てを網羅的にチェックしたい」といった場合に使えます。Yes or…
細かく1つのコードごとに何をしているかを書き下しているおかげで、この記事の6を写経していくと「わかる、わかるぞ…!!」と感動。
![](https://doctor-koala-blog.com/wp-content/uploads/2023/02/B3E652CD-DF0B-4454-84DC-196B0575D187-150x150.png)
マイベスト・オブ・分かり易い記事!
いざ、実践!
「bit全探索 atcoder」などと検索すれば、過去のどの問題がbit全探索で解くことができるのかを調べることができます。それらの問題に挑戦して手慣らしをしてみました。
ABC197CはPythonでは制限時間内に解けず、TLEになってしまったのですが、これもググって「PyPy」なるもので行えば良い、と知恵を拝借し、無事正解(AC)できました。
![](https://doctor-koala-blog.com/wp-content/uploads/2023/02/B3E652CD-DF0B-4454-84DC-196B0575D187-150x150.png)
![](https://doctor-koala-blog.com/wp-content/uploads/2023/02/B3E652CD-DF0B-4454-84DC-196B0575D187-150x150.png)
![](https://doctor-koala-blog.com/wp-content/uploads/2023/02/B3E652CD-DF0B-4454-84DC-196B0575D187-150x150.png)
コードを全く書き換えず、ただ「PyPy」として提出するだけで爆速!
どんな問題がbit全探索で解けるのかを知りたい人、ACコードに興味がある人はぜひコードを見ていってね!
Gistのリンクを置いていきます。
![f:id:mountkoara:20210505162326j:plain](https://cdn-ak.f.st-hatena.com/images/fotolife/m/mountkoara/20210505/20210505162326.jpg)
![f:id:mountkoara:20210505162326j:plain](https://cdn-ak.f.st-hatena.com/images/fotolife/m/mountkoara/20210505/20210505162326.jpg)