数学を学ぶ

競技プログラミングと関連が深い数学の基本的な知識に加えて、高度な内容を解説・証明した記事も掲載しています。

出題される分野・キーワード

AtCoder Beginner Contestで最低限理解する必要がある（と感じた）数学的知識 - AtCoder Beginner Contest (ABC)に参加する上で、よく出題される数学的知識をまとめた記事。
150分で学ぶ高校数学の基礎 - 高校数学の基礎を概観したスライド。学び直しや先取り学習に取り組むときに、最初の教材としておすすめ。
アルゴリズム・AtCoder のための数学【前編：数学的知識編①】 - アルゴリズムや競技プログラミングと関連が深い数学的要素を総整理した記事。以下の続編もある。
- 【中編：数学的知識編②】
- 【後編：数学的考察編】
参考

超大作の記事であるため、必要に応じて該当する部分を参照するとよいと思われる。
競技プログラミングに関係する数学の整理～文系出身や数学苦手erが、もっと競プロを楽しむために～ - 競技プログラミングの問題を解く上で必要となる数学の分野・キーワードなどを網羅的にまとめた記事。

用語や概念の解説・辞典

Cognicull - さまざまな数学用語が分かりやすく解説されているWebサイト。また、自然科学や工学に関する内容も含まれている。
高校数学の美しい物語 - 高校数学に関する内容を分かりやく解説したWebサイト。大学数学の内容についても記事が多数掲載されている。
閑話休題 - 25年以上にわたって数学・物理に関連した挿話・話題を解説しているWebサイト。
オンライン整数列大辞典 (OEIS) - 整数列(各項が整数である数列)に関するオンラインのデータベース。公式、参考文献などの情報も含まれている。
Wolfram Alpha - 数学に関する質問の回答や計算をしてくれるWebサービス。
- 【競プロ Tips】Wolfram Alpha を使いこなそう - 同サービスを利用するにあたり、複雑な式の入力や時間のかかる計算への対処方法が紹介されている記事。

問題集

「中学受験の算数」で磨くプログラミング的思考力！〜親・子供・プログラマすべてに送る 25 問〜 - 「中学受験の算数」を題材とした問題を解きながら、プログラミング的思考力を楽しく鍛えられる。
競プロのための算数・数学 - 競技プログラミングの問題を解く上で必要な算数・数学の基礎知識を演習問題を通して身につけることができる。

数式を書く・読む

数式が多い解説の読み方

「数式の多い解説」の読み方について - 数式がやや多めに書かれている解説を題材に、drkenさんが読み解くコツを紹介している記事。

記事で数式を書く

競技プログラミング記事を書きたい人のための数式の書き方入門 - 著名な組版処理システムTeXにおいて、基本的な数式の書き方・作法が紹介されている。

整数

床関数・天井関数

切り上げ処理〜 (a + b - 1) / b とは何か〜 - 切り上げ処理を1行で書くための方法と、その妥当性が解説されている。
- a / b の切り上げ処理が (a + b - 1) / b でうまくいく絵本 - 上記の内容をより身近な題材を通して図解している。
床関数・天井関数（floor function / ceiling function）の典型まとめ - 床関数・天井関数の定義、不等式評価、切り捨て除算による実装例、オーバーフローを回避した大小比較などがまとめられている記事。

素数・素因数分解

AtCoder版！マスター・オブ・整数 (素因数分解編) - 整数を扱った問題のうち、「素因数分解」に焦点を当てた記事。素数の判定、約数列挙、素因数分解の基本と応用などについて解説されている。
エラトステネスの篩の活用法を総特集！〜高速素因数分解・メビウスの反転公式〜 - 素数を列挙するアルゴリズムであるエラトステネスの篩について特集した記事。同アルゴリズムの基本から応用例まで幅広く紹介されている。
- エラトステネスの篩の高速化 - さまざまな方法でエラトステネスの篩の高速化・省メモリ化が図られている(全6回)。実装例は、C++11。
ミラー・ラビン素数判定法 - 素数を判定するアルゴリズムの概略と証明が掲載されているスライド。
Prime CountのPDFを書きました - 素数の個数を求めるアルゴリズムであるMeissel-Lehmer Algorithmとその高速化方法について紹介した記事。
線形篩で遊ぼう - 線形時間で前計算を行い素数の判定・列挙を高速に処理する方法と、その応用例が紹介されている。
素数に関する上からの評価（初等的な証明） - 素数の個数や逆数和の計算量評価のうち、「弱い評価」について証明した記事。

最大公約数

AtCoder版！マスター・オブ・整数 (最大公約数編) - 整数を扱った問題のうち、「最大公約数」を特集した記事。前半ではEuclidの互除法について、後半では「互いに素」の性質について、それぞれの解説と例題がまとめられている。

拡張ユークリッドの互除法

拡張ユークリッドの互除法〜一次不定方程式 ax + by = c の解き方〜 - 一次不定方程式ax + by = cの整数解を求めるアルゴリズムである「拡張ユークリッドの互除法」について解説した記事。

剰余 (mod)

競技プログラミングにおける剰余の基礎と mod 逆元 - 剰余の基本的な性質から逆元の考え方・C++の実装例が解説されている記事。
「1000000007で割ったあまり」の求め方を総特集！〜逆元から離散対数まで〜 - コンテストで頻出の「1000000007で割ったあまり」を求める問題への対策をまとめた記事。このような問題が出題される理由の説明から、四則演算・累乗・二項係数など幅広い話題について解説されている。
- 任意 mod で二項係数を列挙する - 任意の剰余に対して、二項係数を高速に列挙する方法が解説されている記事。問題の論点、解法だけでなく、C++による実装例も紹介されている。
有理数 mod はこわくない - 「有理数をmodで扱う」問題を解くために、定義を理解するための言い換えと四則演算が紹介されている記事。
有理数 mod 998244353 の徹底解説！ - 有理数p / q (mod 998244353)について、丁寧な解説とAtCoder Library (ACL)による実装方法が紹介されている。
中国剰余定理 (CRT) の解説と、それを用いる問題のまとめ - 中国剰余定理を特集した記事。概念の説明および証明、アルゴリズム、応用例などが解説されている。

組合せ

順列

競プロerのための群論 (swapと順列と対称群) - 競技プログラミングにおけるswapや順列に関する問題を群論（特に対称群）の視点から捉えることを目標にした記事。群論の入門という位置付けにもなっている。

数え上げ

「写像12相」を総整理！〜数え上げ問題の学びの宝庫〜 - 条件を満たすものを数え上げるタイプの問題(「数え上げ」の問題)で登場する写像12相を整理した記事。写像12相の中でも特に高度な内容とされる「スターリング数」と「分割数」の解説および実装について紙面が割かれている。また、写像12相に関連する例題のリンクも掲載されている。
「積の和」典型の、最も典型的な問題 - 「積の和」に関する最も典型的な問題について、組合せ論的な解釈と多項式・形式的冪級数による方法が紹介されている。
上限付き単調増加列の数え上げ - 単調増加列や括弧列の数え上げを経路の数え上げ問題に帰着し、分割統治法で解く方法が紹介されている。

組合せ論

月刊組合せ論 Natori - 筆者が面白いと感じた組合せ論のトピックが紹介されているブログ。

もっと読む

三角関数

三角関数は何に使えるのか〜サイン・コサイン・タンジェントの活躍〜 - 三角関数の意義や使いどころを特集した記事。

幾何

三角形の頂点の座標から五心の座標を求める - 三角形の頂点の座標から、五心(重心・外心・内心・垂心・傍心)を求める方法を解説した記事。C++での実装も紹介されている。
プログラミングコンテストにおける計算幾何入門 - 幾何問題(平面/空間上で図形を処理する問題)の構成要素、基本的なアルゴリズム、応用的な用法・実践例などが解説されている資料。

発展的な内容

調和級数

調和級数などのはなし - 「調和級数」と「割り算で出てくる項数」の計算量解析とその証明が紹介されている記事。

離散・高速フーリエ変換

離散フーリエ変換(DFT)の仕組みを完全に理解する - 高速フーリエ変換の前提知識である「離散フーリエ変換」の原理・公式の導出を丁寧、かつ、分かりやすく解説することを目指した記事。
【競プロer向け】FFT を習得しよう！ - 競技プログラミングの文脈における高速フーリエ変換の説明と、同変換を活用した畳み込みについて解説されている記事。
競プロのための高速フーリエ変換 - 離散フーリエ変換・高速フーリエ変換の解説とC++による実装が紹介されている記事。
FFT（高速フーリエ変換）を完全に理解する話 - 高速フーリエ変換について、丁寧に解説された記事。記事を読む前提として、数IIまでの知識が求められる。
[数学・numpy] 高速フーリエ変換(FFT)による畳み込み - 競技プログラミングで高速フーリエ変換を活用するための基礎知識が整理されている。Pythonのライブラリnumpyを利用した実装例もある。
高速フーリエ変換の実装を難しそうかなと思っている方が、なんだ簡単じゃないですか！！となるための実装講座です - 高速フーリエ変換の知識があることを前提に、実装方法に重点を置いた解説記事。C#での実装例もある。
NTT(数論変換)のやさしい解説 - 高速フーリエ変換の応用例の一つである数論変換(Numeric Theory Translation)について解説されている記事。

形式的べき級数

形式的べき級数 - 組合せ論および形式的べき級数の概略を解説している。
形式的べき級数解説 - 数え上げの問題を、多項式・形式的べき級数の問題に言い換え、代数的な式変形から解答を得る手法をまとめた記事の一覧。また、関連リンクも充実している。
- 誰でもなんとなく理解できる形式的冪級数 - 形式的べき級数の概念・解ける問題を例題を用いて平易な言葉で解説している記事。
- AtCoderで解ける形式的べき級数問題を集めました - AtCoderの過去問で、多項式・形式的べき級数を活用して解ける問題とそれらの解説へのリンクがまとめられている。
二項係数の和の処理（形式的べき級数） - 数え上げテクニック集で掲載されている「14.1 頻出公式集」を形式的べき級数などを用いて証明した記事。前提知識として、形式的べき級数の定義や基本的な演算方法に対する理解が求められる。
【競技プログラミング】形式的冪級数の応用テクニック(前編) - 数え上げなどの問題を解くときに用いられる「形式的冪級数」の応用テクニックをまとめた記事(hotman78さん)。前提知識として、フーリエ変換や形式的冪級数の基礎について理解していることが求められる。
- 【競技プログラミング】多項式のGCDを O(N(logN)^2) で行う方法(half GCD) に関して解説！【暫定版】 - 多項式GCD(2つの多項式を両方割り切る次数最大の多項式)を高速に計算するため、half GCDを用いる方法が紹介されている。
【競プロer向け】母関数を習得しよう！ - 数え上げの問題に対して、数列を母関数に変換して考察するテクニックが解説されている記事。

Monge性

[Monge まとめ①] Monge 性とは？ - Monge行列の定義、性質、用途、具体例がまとめられている記事。
Mongeの手引書 - Monge行列の定義、解釈の方法、例題(単一始点最短経路問題とその一般化)、オンライン・オフライン変換やLARSCH algorithmの解説など幅広い話題がまとめられているスライド。

参考

Monge性に関する内容を読みたい場合は、99ページ以降を参照されたい。