場合の数と整数を復習しつつ入緑した (atcoder)

3年かけて緑に行けました…

0. 背景

入緑の記事は沢山ありますが、自分が観測できる範囲では、「場合の数」と「整数」に焦点を当てた入緑記事は少ないように思います。そこで、「場合の数」と「整数」にスポットを当てて、入緑になる方法を紹介しようと思います。具体的には、「場合の数」と「整数」に関する参考書を紹介していきます。推測になりますが、atcoderに参加する人達は、早慶や旧帝大やそれらのレベルに匹敵する大学に通っている人達or卒業した人達が、高レートのほとんどを占めているのではないかと思います。彼らにとっては、嫌というほど受験勉強時に取り組んだ当たり前でも、私のような受験勉強をなあなあにした人間には、「場合の数」と「整数」は当たり前ではないです。(受験勉強から逃げたのだから、「場合の数」と「整数」が苦手なのは当たり前と言えますが。)

1. 場合の数の総復習

これを2019年ごろからコツコツやりました。これが緑に大きく寄与したのではないかと思っています。
場合の数の復習する経緯としては、

1.適切な時間計算量を見積もることができない。(O(N!)なのか?O(NのN乗)なのか?その違いが曖昧でした。)
2.樹形図を描いて、そこからDFSに落とし込むことができない。

を克服したく、場合の数に慣れることを目指しました。うまく言葉で言えないのですが、樹形図を苦なく書く訓練ができていないと、DFSに落とし込み、メモ化再帰に書き換えることは難しいのではないかと思います。僕がそうでした。そして、時間計算量を正しく見積もれないと、本来なら通せたはずなのに、提出を躊躇うことも出てきます。これは勿体無いです。

「樹形図を書くこと」や「愚直に数えること」に慣れていないと、実践・最強最速のアルゴリズム勉強会第三回講義資料(ワークスアプリケーションズ & AtCoder)というスライドも理解できないと思います。このスライドには、N個のりんごをM人に分ける通りは、何通りあるか?という話があります。そこから、メモ化再帰に繋げた話があります。僕は、N個のりんごをM人に分ける通りの求め方が理解できませんでした。

また、効率よく数えることに慣れていないと、D - Bouquetも分からないと思います。分からなかった方向けに、けんちょんさんという方がこの問題に対する解説を行っています。
けんちょんさんによる解説記事：2020-04-22 AtCoder ABC 156 D - Bouquet (緑色, 400 点)

多分、解説記事を読んでも意味不明だと思います。これは、「場合の数」に対する基礎知識が不足しています。必要ベースで「場合の数」をつまみ食いするのもアリですが、「場合の数」の基礎がボロボロの状態では、つまみ食いしたところで理解できないと思います。

※「効率よく数える」とは、2のn乗とか、nCkとか、nPkなどを駆使して、場合の数を求めるやり方のことをここでは言っています。

「愚直に数える(例えば樹形図を書き、枝の本数を数えるとか。)」と「効率よく数える手法」を学ぶことは、競技プログラミングの基礎になるのではないかと思います。場合の数に関するお薦め本を以下にまとめます。

合格る確率+場合の数 (大学受験合格る)
ハッとめざめる確率
 マスター・オブ・場合の数―大学への数学
 解法の探求・確率―大学への数学
 数学場合の数・確率分野別標準問題精講

特に、

1.ハッとめざめる確率
2.合格る確率+場合の数 (大学受験合格る)
3.マスター・オブ・場合の数―大学への数学

を重宝しました。ただし、マスター・オブ・場合の数―大学への数学は半分程度しか、きちんと解けていないです。それでも、緑に寄与するぐらいの貢献度はあったと思います。

「基礎編」、「演習編」という分類別に分けて、詳細を書いていきます。１冊ずつ読んでもいいのですが、複数の本にまたがって行ったり来たりする勉強法でもいいと思います。

1-1.基礎編

合格る確率+場合の数 (大学受験合格る)

癖のない本です。そして、「場合の数」について膨大な例題が用意されています。加えて、似た類題も用意されています。ただ単に膨大なだけでは、読む価値はありませんが、様々な概念に絡んだ例題が数多く用意されています。具体的には、愚直な数え上げ、重複順列、組み合わせ、包除原理、最短経路、漸化式による数え上げ、ボールと箱の対応関係(ボールを区別した場合の通り数とか、箱を区別しない場合の通り数とかのやつ)、などが網羅されています。他にもあります。気になる方は近くの書店で手に取ってみてください。受験コーナーにあると思います。この本さえ読めば、「場合の数」に対する苦手意識はなくなっています。もちろん、演習は必要です。

ハッとめざめる確率

他の本で「場合の数」が理解できなかった人向けの本です。この本はとても癖のある書き方がされていて、最初は読みづらいかもしれません。「合格る確率+場合の数 (大学受験合格る)」とセットで読むといいです。タイトルに確率とついていますが、「場合の数」についてもガッツリ触れています。

解法の探求・確率―大学への数学

正直なところ、合格る確率+場合の数 (大学受験合格る)、ハッとめざめる確率、マスター・オブ・場合の数―大学への数学を手元に置いておけば、もう十分です。お金に余裕があれば、この本を買ってもいいかもしれません。優先度は低いと思います。

1-2.演習編

マスター・オブ・場合の数―大学への数学

「合格る確率+場合の数 (大学受験合格る)」と「ハッとめざめる確率」で基礎が身についても、初見で問題が解けるようにならなければ、意味がありません。atcoderで遭遇する問題に対して、正しく時間計算量を見積もることや、樹形図を書くには、基礎を読むだけではできるようにはならないです。ですから、演習は大事です。普通の演習書では、「合格る確率+場合の数 (大学受験合格る)」と被ってしまうのですが、「マスター・オブ・場合の数―大学への数学」は、atcoderに出てくるような変わってる問題も沢山用意されています。参考書はページ数は少ないのですが、中身はとても濃いです。写像と絡めたマニアックな話もあり、読んでおいて損はないです。

数学場合の数・確率分野別標準問題精講

「マスター・オブ・場合の数―大学への数学」で自信を無くした人向けの本です。自分は「マスター・オブ・場合の数―大学への数学」が難しく感じ、一旦こちらを経由しました。「俺つえー」を感じることも、継続には必要だと思います。そのために用意しておきましょう。

2. 整数の総復習

こちらは、場合の数よりは優先度が低いのではないかと思います。理由はdfsの実装や時間計算量の見積りの方が、競技プログラミングにおいて、大事な要素だと思ってるからです。整数に関しては、正直なところ、atcoderの問題を解くために学んでおく必要があるという側面が強い気がします。ですから、場合の数が苦手なら、まずはそちらの復習をやっておくと良いです。

改訂第2版佐々木隆宏の整数問題が面白いほどとける本 (数学が面白いほどわかるシリーズ)
数学ガールの秘密ノート／整数で遊ぼう
 マスター・オブ・整数―大学への数学

個別に紹介していきます。「基礎編」、「演習編」という分類別に分けて、詳細を書いていきます。

2-1.基礎編

改訂第2版佐々木隆宏の整数問題が面白いほどとける本 (数学が面白いほどわかるシリーズ)

この本は超超超基礎的な整数の入門書です。これを読んでも、整数に強くはなれません。ですが、整数に出てくる用語に暗記するぐらいには慣れておかないと、話になりません。整数の用語を見るだけで、震えが止まらない人は、こちらの本を読んでおくと良いです。

数学ガールの秘密ノート／整数で遊ぼう

コーヒを飲みながら、読みましょう。整数に取り組むのは疲れます。僕は逃げ出したくなりましたが、数学ガールのおかげで、理解した気にはなれます。そういう誤魔化しも、継続には大事な要素です。

2-2.演習編

マスター・オブ・整数―大学への数学

この本は、「マスター・オブ・場合の数―大学への数学」と対をなす本で、受験界隈では有名な本のようです。この本もやはり、読んでおくべき本だと思います。私は恥ずかしながら、完全には理解できておらず、今もなお時間がある時に読んでいる本です。この本のおかげで、atcoderで初見の問題に遭遇しても、「とりあえず実験してみればなんとかなるっしょ」という忍耐力はつきました。(そういう目的の本ではないと思いますが…)

3. まとめ

どうでしたかね…微妙な記事になっていたらすみません。他にこんな参考書もおすすめだよ!!という意見がありましたら、コメントをお願いします。追記しておきます。