競技プログラミングに関係する数学の整理 ～文系出身や数学苦手erが、もっと競プロを楽しむために～

まえがき

この記事では、競技プログラミングに関係する数学用語・概念と、それがどんな単元（分野）に属するものかを整理（一覧化）します。
競技プログラミングの問題に出てくる用語・概念をはじめ、競技プログラミングの解説記事などに出てくる用語・概念も、思いつく限り挙げています。

「この記事の数学的な部分、どのぐらい信用できるの？」とか、「数学苦手と言ってもどのくらい苦手なの？」といった疑問への参考としては、筆者のバックグラウンドを記事の最後で紹介したので、気になる方は先にそちらを読んでください。

この記事の目的

文系出身や数学苦手erで、「難しい数学をやらずに」競プロを楽しむ、という取り組み方をしている方もいると思います。
それはアリだと思いますし、それでもやり方や本人の能力次第で水コーダー以上になることはできると思います。

ただ、「数学ができたらもっと楽しいだろうにな……」とか「もっと強くなれるだろうにな……」と思っている方も多いはずです。
そういう方の中には、過去の私と同じように、「競プロをもっと楽しむために、少しずつでも、数学を学んでいきたい！ でも、何を勉強すればいいの？」という方もいるのではないでしょうか。

今回は、そういう方の参考になるように、自分が水コーダーになるまでに出会った（・学んだ・これから学ぶ）数学的知識・考え方を、用語と単元（分野）の観点から自分なりに整理してみます。

意図する対象読者

文系出身だったり、数学が苦手だったりして、競プロでは数学が必要になると聞いて、不安に思っている方。
もしくは、競プロでは数学が必要になると聞いて、「よっしゃ！ そんならバリバリ数学勉強してアド取ったるわ！」と思っている方。

また、「競プロや競プロ記事で知らない数学用語が出てきて、用語名でGoogle検索したもののイマイチ分からず、基礎から学びたいと思っているのに、そもそも何の分野なのかよく分からなくてうまく勉強できない」という方。
（このシチュエーションが今まで何回あったことか……）

今回の整理の仕方（記事の見方）

競プロをやっていく中で「あれっ、これ何だろう？」となった時、必要な知識に辿り着けるように、逆引き形式で整理します。
つまり、「競プロで出会う言葉や、必要になる式変形など」を挙げ、「それがどのような数学の分野に当たるか」を記載します。

注意

一覧を見て、「こんなに勉強しないといけないのか……」と思わないでください。
「あれっ、これ何だろう？」をできる限り解決するため、沢山のことを一覧に載せましたが、どれも「うーん、これは今はいいや！」と飛ばしても、特に問題無いはずです。

また、数学の分野名は基本的にできるだけ新しい教育課程を参考にしましたが、コロコロ変わってるのと、それほど真面目に調べてないので、ちょっとズレてる場合があると思います。
例えば、数学Ⅰと書いてあるけど今は数学Ⅱに移っている、など。
そのため、勉強のために検索する際は、「数学Ⅰ」「数学Ⅱ」といったくくりより、単元名を使うことをおすすめします。

競プロに関係する数学（本題）

「言葉（文系でも多分聞いたことはある）」編、「言葉（文系だと聞いたことないかも）」編、「言葉（離散数学）編」、「式変形」編、「図形っぽいやつ」編に分けます。
前者2つはそのまんまですが、後者2つは、「この式変形何？」と思ったときと、「これ図形関係っぽいけど何？」と思ったとき用です。

「離散数学」とは、文系の方は聞き慣れないかもしれないですが、競プロ及び情報学に最も深く関わる学問分野です。
自分は、この「離散数学」が深く関わっているということに気付くのに1年くらいかかりました……。
それが分かってからはGoogle検索などもしやすくなり、本も探せるようになったので、物凄く勉強が捗るようになりました。

なお、「競プロの問題では出てこないけど、競プロの問題の解説記事で出てくる言葉」もバンバン載せています。
逆に、「アルゴリズム」に属すると思われる言葉は省きました。

言葉（文系でも多分聞いたことはある）編

・素数、素因数、素因数分解、自然数、約数、倍数、公約数、公倍数、ユークリッドの互除法など … 小5～中1あたりの「数と計算」「数と式」、数学A「整数の性質」。難しくなってくると整数論という（？） 競プロでは超メジャー分野なので、基本、とりあえず出てきたワードで検索すれば目的のものに辿り着く
・方程式、方程式の解、連立方程式、不等式など … 中1～3の「数と式」「関数」、数学Ⅰ「数と式」、数学Ⅱ「いろいろな式」など。かなり多岐に渡るので、この辺りを押さえようと思うと、Google検索つまみ食いじゃなくて、入門本を1冊買った方がいいと思う
・関数（y=axみたいな形のやつ）、二次関数、関数の最大値・最小値・極大値・極小値、定義域、値域など … 中1～3の「関数」、数Ⅰ「二次関数」、数学Ⅱ「指数関数・対数関数」「三角関数」、数学Ⅲ「極限」
・累乗、べき乗（冪乗）、階乗 … 似たような言葉ですが、累乗・べき乗は数学Ⅱ「指数関数・対数関数」に関わる言葉で、階乗は数学A「場合の数の確率」で出てくるものです。また、「べき（冪）」はもっと一般化して難しい意味で使うこともある（理解していません）ようなので、「なんか意味が噛み合わないな？」と思ったらそういうことかもしれません。
・数え上げ、順列、重複順列、組み合わせ、独立、条件付き確率、nCk、nPk、n!、玉と仕切り、写像12相などなど … 数学A「場合の数と確率」、難しくなると「組み合わせ論」などと呼ばれるらしい

・平均値、中央値、期待値、分散 … 中1～3「資料の活用」、数学Ⅰ及び数学活用「データの分析」
・期待値の線形性 … 緑Diffくらいから出てきます。これは式変形に関することなので、式変形編に載せます。

言葉（文系だと聞いたことないかも）編

・二項定理、二項係数、パスカルの三角形 … nCkに関する言葉でもあります。数学A「場合の数と確率」、数学Ⅱ「いろいろな式」。これは競プロ頻出で良記事が多いので、Google検索で詳しい記事を探すのが良いです。
・単調増加（減少）関数、凸関数、凹関数など … 二分探索とか三分探索を勉強すると出てきます。これは関数の形に関する言葉ですが、上記の関数関連分野の中の数学Ⅰ～数学Ⅲエリアで出てきます。
・微分、積分、導関数、二階微分など … 数学Ⅱ「微分・積分の考え」、数学Ⅲ「微分法」「積分法」、難しくなると解析学というらしい？
・ベクトル … 数学B「ベクトル」。ただ注意が必要で、大学以上の数学である「行列（線形代数学）」に踏み込んだ意味で使われている場合がある。また、線形代数学に深く踏み込んで、「代数学」を勉強しないと分からない意味で使われている場合もある。
・行列、線形代数、掃き出し法、消去法、拡大係数行列、行列累乗、連立一次方程式の解、ピボット、行基本変形、基底、標準形、ベクトル空間、行列のrankなど … 数学B「ベクトル」の発展型で、大学以降の「線形代数学」分野。また、線形代数学は「○○代数学」とついている通り、離散数学の「代数学」をかじってないと分かりにくい話がたまに出てくる感じがしてます。
・漸化式 … DP（動的計画法）でよく出てきます。数学B「数列」。
・数列、等差数列、等比数列、等差数列の和、一般項など … 数学B「数列」、数学Ⅲ「極限 - 無限等比級数の和」など
・極限、lim、収束、発散など … 数学Ⅲ「極限」「微分法」「積分法」
・有理化 … 中3「平方根」
・log、ln、対数、自然対数、e、ネイピア数、指数、次数など … 数学Ⅱ「指数関数・対数関数」、数学Ⅲ「微分」（※自然対数、e、ネイピア数 及び ln が数Ⅲ範囲。とはいえ、数Ⅱの知識があればGoogle検索で雰囲気は掴めると思います）

言葉（離散数学）編

・逆元（a^(-1)） … 逆元は、「mod P でのあまり」を求める時に出てきて困った人が多いと思います。離散数学の「代数学」分野です。
・単位元（e）、モノイド、半群、群、環、体、類、代数系、多項式、交換律、結合律、二項演算、「閉じている」などなど … 競プロ記事で出てきて「何だこれ」ってなる文系が多いと思います。セグ木の抽象化でも出てきます。これも離散数学の「代数学」分野です。この辺りの「いやなんか全然聞いたことないけど！？」みたいな単語がバシバシ出てくる記事があったら、代数学を前提としてることが多いです。ちょっと大変ですが、これをやると一気に読める記事が増える（特に、青色以上の猛者の記事が読める）のでオススメです！ 競プロの楽しみが広がります！
・フェルマーの小定理、位数、原始根 … これも「代数学（整数論の方でも出てくると思う）」の一分野に属しているようです。代数学の「剰余類」「巡回群」辺りの言葉をやった後なら、なんとか話が追えると思います。
・∀、∃、集合、有限集合、要素、元、部分集合、∈、「N」「Z」「Q」「R」「C」、和集合、積集合、補集合、ド・モルガンの法則など … 数学Ⅰ「数と式 - 数と集合」にもありますが、離散数学の「集合」分野で詳しく出てきます。
・真、偽、命題、述語論理式、論理和、論理積、否定、¬、∧、∨、論理式、同値、⇔、逆、裏、対偶、十分条件、必要条件、必要十分条件、数学的帰納法、背理法など … 数学Ⅰ「数と式 - 数と集合」にもありますが、離散数学の「論理」分野で詳しく出てきます。また、明確には表れてこないものの、この辺りの話を追っていると、「競プロer（というか数学に強い人）の書く日本語」の特徴に少し慣れることができ、問題を読む速度が上がります。
・直積集合、直積、関係、（関係の）合成、同値関係、同値類、代表元、剰余類、写像、関数、定義域、値域、像、単射、全射、全単射、置換、置換の積、濃度、加算濃度、可算集合、無限集合、離散集合などなど … 特に写像や関数、○射あたりは、数学に強い人の記事でよく出てきます。離散数学の「関係と写像」です。
・上界、下界 … 代数学の「順序集合」に出てくるようですが、まだやっていないため不明です。
・グラフ、点、頂点、辺、端点、ノード、多重辺、部分グラフ、次数、隣接行列、経路、パス、道、閉路、サイクル、有限グラフ、連結、非連結、完全グラフ、2部グラフ、完全2部グラフ、マッチング、フロー、木、全域木、根、根付き木、葉、枝、深さ、彩色、頂点彩色、オートマトンなどなど … 離散数学の「グラフ理論」に出てくる言葉です。と言っても、グラフ理論は明らかによく出てくるので、勉強している人が多いと思います。まだ「ちょっと難しそうだしな～」と思って尻込みしている人がいたら、分かりやすい記事がネットに沢山転がってますので、ぜひ勉強してみてください。

「式変形」編

・長い式を（x+1)(x^2+x+1) みたいに分けるやつ … 因数分解（中3 数と式）
・「√」に関わる式変形 … 中3「数と式 - 平方根」、数学Ⅱ「指数関数・対数関数」
・「x^k（xのk乗）」に関わる式変形、特に「x^(a+b) = (x^a)*(x^b)」的なやつ … 緑～水Diff以降でかなり出てくるので、重要な式変形だと思う。中3「数と式 - 平方根」、数学Ⅱ「指数関数・対数関数」
・「Σ」に関わる式変形、特に「○○数列（○○級数）の和なので、以下の式になる」的なやつ … 数列の問題めちゃくちゃ多いので、これは重要。数学B「数列」、数学Ⅲ「極限 - 無限等比級数の和」など
・「Σ」や「期待値（E）」や「平均」に関する式について、「線形性」「期待値の線形性」を使って…… と言いながら、なんかサラッと式を分解してくるやつ … 水コーダーを目指すに当たっては押さえた方がいい式変形だと思います。数学B「数列」分野ですが、教科書等で簡単におさらいしたあと、「期待値の線形性」などでGoogle検索して、詳しく解説した記事を読んだ方がいいと思います。
・←この記号（Π。πの大文字） … 式変形ではないですが、詰まりがちなので入れました。大体の数学記号はGoogle検索で記事が出てくるのですが、コイツはすごく面倒で、どうやら「代数学の集合や関係の分野で出てくる『直積集合』」の意味と、「数列で出てくるΣ（総和。数列の全てを足し算したもの）の掛け算バージョン（総乗。数列の全てを掛け算したもの）」の2つの意味があります。どちらの意味になるかは、文脈次第です……

「図形っぽいやつ」編

・諸々の公式を理解するための前提 … 中1～3「図形」
・三角比、正弦定理、余弦定理など … 数学Ⅰ「図形と計量」
・図形に関する方程式、円と直線、点と直線の距離、線分の交差判定などなど … 数学Ⅱ「図形と方程式」。数学Ⅰ「図形と計量」、数学Ⅱ「図形と方程式」を必要に応じておさらいしつつ、「幾何ライブラリを作る」というような記事を探すといいと思います。
・三角関数、sin、cos、tan、asin、acos、atan、ラジアン、rad、θなどなど … 数学Ⅰ「図形と計量」、数学Ⅱ「図形と方程式」、場合によっては数学Ⅲ「平面上の曲線と複素数平面」も？
・複素数、複素数平面、直交座標、極座標、ベクトルの回転などなど … 数学Ⅲ「平面上の曲線と複素数平面」
・凸包 … 大学レベルの図形だと思うけどよく分かってません

筆者のバックグラウンド

ひとくちに文系出身・数学苦手erと言っても、その中でも多種多様な人がいるわけで、その辺り私はどうなの？ というところを紹介しておきます。
ざっくりまとめれば、「ほんとは苦手というほどでもないけど、競プロ界ではかなりの数学弱者の部類。特に整数については弱者だった」です。

経歴、仕事など

名古屋大経済学部出身、専攻は経済史（まあ歴史です）、今は30代の公務員（事務職、つまりいわゆる普通の公務員）です。
前職は高校生相手の学習塾講師（英語と、たまに国語）でした。

入試の二次試験には数学があったので、数ⅡBまではある程度勉強しました。
とはいえ、英語と国語で点数を稼いだ（前職で高校生に英語と国語を教えていることからも分かる通り）ので、数学が得意とは到底言えません。

とは言え、一般社会における意味での数学苦手erかというと、そういうわけでもないです。
全国模試の偏差値で言うと 50 ~ 60、センター試験本番の点数で言うと、数ⅠA 88点、数ⅡB 36点です。

学習塾時代の経験を踏まえてできる限り客観的に自己分析をすると、「数学をしっかり勉強したとは到底言えないけど、できないわけでもない、フツーの（ただし高校の国公立文系志望コース（≒数ⅡBの履修）を経た）比較的真面目な文系大学生」くらいであり、「競プロ界では、物凄く不利とまでは言わないが、かなり不利な部類」というところではないでしょうか。

また、ゆとり教育（というものが昔ありました）世代のため、数学Aの「整数の性質」（合同式、mod、ユークリッドの互除法……）を学んでいませんでした。
これはかなり競プロで苦労する原因になりました。

ただ、名古屋大学の二次試験で、なぜかやたらめったら確率漸化式（漸化式の仲間）が出題されていたので、確率と漸化式は結構頑張って勉強していました。
それは競プロにも生きていると思います。