こんにちは。リユナと申します。競プロでは考えより数学問題が結構出ますよ。今日はこれらをどう接近して解くのか、これらをためにどう勉強したらいいのかについて話そうとします！
0.初めに
私は数学科です。これについてはいつも誇らしく考えています。だって、私は数学が大好きだからです。実はそれで競プロのための数学を別に特に勉強したりしてませんでした。むしろチーム大会ではいつも数学担当の役をしました。今回のICPCではかなり自分の役目を果たして嬉しかったです！
数学が大好きって、実はえぐいですよね。これに共感できない方が本当多くいらっしゃると思います。多分多くに人には競プロをやるために仕方がないから数学にちょっとだけ手をさわったと思います。
競プロについて数学って、いや、実はコンピューター科学と数学は今になっては相互補完的な関係だと言えます。 難しい数学難題がコンピュータを通じた計算で解けたり、逆にコンピュータ科学での暗号化、圧縮のような分野で整数論などが使われることもあります。数学の世界にちょっとだけ手を出したら、本当に成長している自分を見つけられるかもしれません。数学の問題そのものだけでなくとも、数学的に問題にアプローチする姿勢は、きっと競技プログラミングにも大いに役立つと思うからです。
1.めっちゃ数学の問題を解くためには？
たまに大会では「おおっぴらにこれでいいのかと思うほど数学の問題」である問題が出たりします。例えば、 こんなことがありますね。
今回の記事はこれを解く方法について話す記事ではないので、簡単にコンセプトだけを説明します。この問題の要点は「一度シャツが混ざり始めた以上、このシャツは結局他のどのシャツとも区別できなくなる。」ことです。もちろんそれで終わることではなくて、連れてくるちょっとだけの式を整理して、問題をプログラミングで解くための前処理をちょっとしなければなりません。
あなたが数学科だとか、数学に興味が深いではないならこんな問題を今すぐ直接解けるのは多分ちょっと難しいかもしれません。しかし、私たちはここで「競プロの数学問題でよく使われるアプローチ」などを考えてみます。この問題のように、期待値を求める問題ならある時点からの対称性や「結局、他のものと区別できない」という性質などを使う場合が少なくありません。 そうでなければ、普通はDPで解かなければならない問題です。
こんな問題を多く解いてみたらもちろん最高ですが、私のおすすめの方法は、易い問題でもこんな風の問題を接したことが多ければ、さらに難しい問題でもそのような思考を展開できるという点です。
個人的に考えるよく使われるアプローチはこんなことたちがあります。
・場合の数を求める組合論の問題はもちろん先行知識が必要な場合が多いが、意外と「反対の場合と対称になるため、全体を求めて半分にすればはるかに簡単に手に入れることができる。」のようなことが結構よくあります。
・確率や期待値の問題は大体二つの部類です。全部数学的に計算して割り出すこととか、意外とある範囲以上はDPを使う問題があります。前者の場合はもちろん背景知識が足りなかったら蒸すかしいですが、「ある問題を有名や易い問題でなるべく変える」という戦略はほぼ共通にでます。後者だったら、DPの漸化式が一番大事ですね。「ある状態までの確率」が与えられた時の「その次につながれる可能性」を考えながら接近したらいいと思います。
・余事件、あるいは余事件の確率を求めるアプローチはどこでも常連です。 これはあなたが数学オリンピックをしても、大学入試をしても同じだと思います。 事実上、DP問題である組合論/確率論問題といっても、DP式を「余事件に対して立てる場合」がそのまま解くよりはるかに簡単な場合がかなりあります。
・包除原理はいつも競プロの常連です。ある程度は勉強しておくのが数学の問題でも、その以外の問題でも役に立ちます。
・あとは整数論ですが、、、こっちは本当に式の整理と背景知識の戦いです。ただし、約数の性質、エラトステネスの篩やオイラー関数、素因数分解とこれで約数を割り出す方法、それらを楽に実装する方法などは知っておくと激難しい問題では無ければ本当に役に立ちます。
・なお、mod 998244353で表す問題が本当に多いですが、合同式についても性質はちょっとだけでも勉強したらいいと思います。例えば、「p/q mod 998244353」を割り出す問題だったら、背景知識がなければ迷うと思いますが、「合同式での逆数は自信を掛け算して1になる数」であることを理解していて、あとフェルマーの小定理などを知っていったら998244353は素数だから「p*pow(q, 998244353-2, 998244353)%998244353」をやればいいんです。
・たまにはこれらが結合して出たりもします。確率をp/qで表してmod 998244353などをする問題ですが、これもちょっとだけの整数論知識があったら、すべて求めてmodをする必要はなく、求める過程で続けて残りを取る方がはるかに効率的で、解決にも問題がないことが分かります。
・幾何は。。。これはちょっと別の種目だと思います。😂普通幾何は実装が一番問題ですから。。
2.数学問題ではなくても、数学的な考え方は役に立つ
結局競プロは「与えられた条件でたった一つ確かにある答えを探す。」ということではないですか。AHCなどを抜いたら、「確実に正解ではないけどまあいいこと」などは存在しません。そうです。結局数学と通じるしかないです。数学こそが現在まで人類が成し遂げた論理体系の中で一番美しくて立派なものだから···というと、言い過ぎでしょうか？😂（実は数学もまたとてつもなく不完全な点が多く、むしろそれもまた魅力だと個人的には思います。）
まあとにかく、数学的な接近は数学問題以外の競プロ問題でも役に立ちます。例えば、こんな問題を見てみましょう。数学的に解く方法ももちろんありますと思いますが、普通それを完全に数学問題だとは思いませんね。でも、累積和とかを使いながらどの部分がどれくらい残るか、などを考えるためには数学的な(いわゆる)センスがあったらもっと早くできます。最小公倍数だとか、CHTだとかユークリッド互除法だとか、何かの整数論的な考えを全て精製された過程を経てするのではなくても、(そもそもそんな問題だったらABCのDではなくARCのD程度だったはずでしょう。)そのようなことに接したことがあれば、この問題をどのように解決しなければならないのか早く思い出すことができると思います。
これは一つの例えですが、結局競プロをやったら数学の問題ではない問題でも、数学的なセンスがあればより易く解ける問題が結構あるとおもいます！
3.終えて
大げさに始めたのですが、実は一般論をぶつぶつ言う程度の文だったのかもしれません。そもそもこの記事は「数学問題を解くために必要なあらゆる数学公式」を話すのではなく、「解くための接近方法とその効用」について話すことに近かったからです。前者についてにもいつかは記事をポストはすると思います。
実は何よりも伝えたかったのは「数学に怖がらないようにしよう」ですね。競プロに数学が必要だから嫌いけど仕方なく勉強する。という人々をかなり見ましたが、実はすでに競プロを楽しんでいるなら、あなたは知らず知らずのうちにある程度は数学を楽しんでいると思います！この数学はあなたの試験成績や大学を決めるものでもなく、先生にやらせてやるものでもありません。 結局そのような圧迫がないのを気づいたら、心理的に緊張感も少し軽くなるだろうし、数学をありのままに新しく接することができると信じています。もっと詳しく知っておくといい数学の知識についてのことなら、これからどんどん記事を投稿する予定です。
今回も読んでくださってありがとうございます！
