はじめに
初めまして。
普段AtCoderにPythonで参戦しているハチです。
今回は、数学的考察について初心者でも一から分かりやすく解説していきたいと思います。
実は僕自身、AtCoder歴は現時点で2ヶ月ほどで、まだまだ初心者です。ですが、初心者だからこそ分かる苦悩や引っ掛かりポイントがあると思います。
そこで、自分と同じようにAtCoder初心者でもこれを読めば「数学的考察」について理解できるような記事を書けたらと思います。
また、今回の記事と同じシリーズには以下のような記事もあるので、ぜひ興味があったら読んでみてください。
目次
- 数学的考察とは
- それぞれの数学的考察についての詳しい説明
- その他コラム
- 練習問題
- AtCoderの典型問題(アルゴリズム)とは(超初心者に向けて。読まなくても大丈夫です)
- 超初心者に向けて(超初心者に向けて。読まなくても大丈夫です)
- おわりに
- 参考文献
数学的考察とは
数学的考察とは、「二分探索」「bit全探索」「累積和」などのような具体的なアルゴリズムではありません。数学的考察とは、競技プログラミングで出題されるような数学的感覚を必要とする問題を解く際のコツ、重要な視点をまとめた総称のようなものと言えるでしょう。
しかし、「数学的感覚を必要とする問題」と言われると、とても抽象的で、天才しか手の付けられない代物のような気がしてなりませんね。僕もそう思います。ですが、そのような典型問題として落とし込みにくいような問題たちでさえも、これから紹介する、体系的にまとめられた幾つかのコツを用いることで解法への糸口をつかむことができます。どう手を付けたら良いか全く分からない状態よりかは、遥かに問題を解く上で有利となるでしょう。
ですが、大前提として、まず初めに全探索で処理する方法を考えてみて下さい。全探索でも十分処理時間が間に合う場合(10の7乗程度)は、問題を解くという観点から見れば、数学的考察を行う必要がないかもしれないからです。
それぞれの数学的考察についての詳しい説明
数学的考察を行う上で有効な視点として、以下のようなことが挙げられます。
では、上で挙げたそれぞれの項目について、これから詳しく説明をしていきたいと思います。
パリティ（偶奇）に着目する
以下の記事の説明がとても分かりやすいです。
とりあえず手を動かして法則性(規則性・周期性)を見つける
とりあえず手を動かしてみると、ある一定の周期性を見つけることができる場合があります。以下の記事が参考になります。
上界を考える
最大値を求める問題では、「≤」のように上界を考えてみることで解ける場合があります。以下の記事が参考になります。
不変量に注目する
ある操作を「K回以内行う」とか「好きなだけ行う」とか指定されている問題は、操作ごとに不変なものを考えてみると特徴を捉えられる場合があります。
変数が減らせるか考える
例えばA、B、Cという値が入力として与えられる場合、A、Bのみについて考えれば良かったり、CをAもしくはBによって表せたりする問題などもあります。
剰余(mod)を考える
あまりに着目すると、ある周期性を見つけられるような問題があります。また、modの性質を知っていれば解くことのできる問題などもあります。
ここで、E869120さんが以下の記事で紹介していたとても分かりやすい図を掲載させていただきたいと思います。
その他コラム
正直に言うと、数学的考察についてまとめることはかなり難易度が高いと私は思います。まず初めに、どのような項目に絞って紹介すべきかが悩みどころとなります。あまりに多くの数学的考察を紹介したところで、それら全部について理解し、それらを使いこなすにはとても労力が必要となります。あまりに多くのことについて紹介してしまったことで、結局頭の中が混乱し、どれも使いこなせなかった、と言うことにはしたくありません。そこで私は、ある程度は切り捨てて、より重要と思われる6つに絞って紹介してみました。今回紹介した記事の中には、他にもたくさんの項目について紹介し、とても分かりやすく解説している記事があります。そういった他の記事も読むことで、学びを深めていくことはとても面白いことだと思います。
練習問題
パリティ（偶奇）に着目する
とりあえず手を動かして法則性(規則性・周期性)を見つける
上界を考える
不変量に注目する
変数が減らせるか考える
剰余(mod)を考える
他にも、「アルゴリズムと数学 演習問題集」と言う問題集があり、多くの問題が紹介されているので、興味があったらぜひ解いてみてください。
AtCoderの典型問題(アルゴリズム)とは
今回の記事でなぜ「数学的考察」を取り上げたのかについて説明したいと思います。
理由はズバリ、
AtCoderでレーティングを上げたい！C問題まで解けるようになりたい！と思っている方は、AtCoderで典型問題と言われているような以下のような解き方をマスターすることが重要だと思っているからです。
では、なぜそれが重要なのか？それは、以下に記した典型問題(アルゴリズム)が、大学受験における、「複素数平面」「2次曲線」「極限」「微分法」「積分法」のようなものだからです。
これらを使った解き方の基本をマスターすれば、それなりに点数が取れる、といったある種のボーダーラインとなります。
◎全探索
・二分探索
・bit全探索
◎バケット・連想配列
◎区間分割・連長圧縮
◎グラフ
◎累積和
・数学的考察(幾つか考えるコツがある。偶奇についてなど)
上の中で、◎がついた項目は、(通称)鹿本にかなり優しく丁寧に解説されている典型問題(アルゴリズム)です。これらの典型問題(アルゴリズム)は、ぜひ鹿本を買ってマスターしてください！(けんちょんさんという方が書かれた良書です。C++、Pythonでの実装例が書かれています。)
他にもたくさんありますが、初心者の方はひとまず初心者から脱却するために、上のような典型問題(アルゴリズム)をマスターすれば良いかと思います。ここまで出来れば、あなたも茶コーダーの仲間入りを無事果たすことができると思います。
超初心者に向けて(これから何をしたらよいか)
AtCoder初心者で、何をしたら良いのか分からない方には、以下の本をお薦めします。
こちらは、AtCoderの典型問題についてかなり優しく丁寧に解説されています。また、それぞれの典型問題(アルゴリズム)ごとに例題、練習問題が豊富に紹介されています。かなり鍛えられる良書です。
こちらは、私が初めて手に取ったAtCoder本です。後半の方はかなり難易度が高く、一つ目の本を解くことに注力しました。ただ、AtCoderで必要な入出力方法についてはこちらの本で学びました。
おわりに
ここまで読んで下さって本当にありがとうございました。
さて、どうでしたか。「数学的考察」をマスターすることはできましたか？
もしここが分からない、ここをこうしたらもっと分かりやすい記事になるんじゃない？と思った方、その他何でもコメントを下さると嬉しいです。より良い記事を書くための参考、モチベーションにしたいです。
ですので、今回分かりづらいと感じた箇所があればコメント等を参考に改善、修正をしながら執筆したいと思います。これからもよろしくお願いします。
今回の曲はこちら。何故だかずっと聴いていられます。
おすすめの曲があったらぜひコメント欄に書いてください！楽しみにしています。
参考文献
(スペシャルサンクス)
(その他)