はじめに
ここでは競技プログラミングでよく使うものや知っておくと便利なものについてまとめる。 絶対に正しいとは言えない(保険)。 コード集というよりも、勉強になるウェブサイトのリンク集になりそう。
言語はC++。
よく使うコード集
探索
二分探索
- けんちょんさんのコードを拝借
- 二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜 - Qiita
// ソート済みの配列 vector<int> s; int binary_search(int key) { int ng = -1; int ok = (int)s.size(); while (abs(ok - ng) > 1) { int mid = (ok + ng) / 2; if (s[mid] >= key) ok = mid; else ng = mid; } return ok; }
グラフ
グラフ作成
- グラフの持ち方には
隣接リスト
と隣接行列
があるらしい
// グラフ用の二次元配列 vector<vector<int>> g; int main() { // 頂点の個数nの分だけ配列の長さを確保 g.resize(n); // 辺(頂点u→頂点v)を受け取ってグラフを作る for(int i = 0; i < m; ++i) { int u, v; cin >> u >> v; u--; v--; g[u].emplace_back(v); g[v].emplace_back(u); } }
データ構造
stack
- LIFO(last in, first out)
- 参考:stack - cpprefjp C++日本語リファレンス
stack<int> st; st.push(3); // 追加 st.push(5); st.size(); // 要素数取得 → 2 int a = st.top(); // 末尾参照 → 5 st.pop(); // 末尾削除
queue
- FIFO(first in, first out)
- 参考:queue - cpprefjp C++日本語リファレンス
queue<int> que; que.push(3); // 追加 que.push(5); cout << que.size(); // 要素数取得 → 2 int a = que.front(); // 先頭参照 → 3 que.pop(); // 先頭削除
算数・数学
最大公約数(gcd)
- いわゆるユークリッドの互除法(名前がカッコいい)
- けんちょんさんのコードを拝借
- AtCoder 版!マスター・オブ・整数 (最大公約数編) - Qiita
int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a % b); }
二項係数(nCk)
- けんちょんさんの記事を参考
- よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方 - けんちょんの競プロ精進記録
- コードは、けんちょんさんの記事から拝借する
modの話
- 「1000000007で割った余りを出力せよ」と言われたときの話
- 参考1:1000000007で割ったあまりを求める問題勉強メモ - Qiita
- 参考2:数学的な性質 Wiki - yukicoder
long long mod = 1000000007; int main() { long long ans = 0; // 足すたびにmodをとる for(int i = 0; i < n; ++i) { cin >> t; ans += (t % mod); ans %= mod; } // 掛けるたびにmodをとる for(int i = 0; i < n; ++i) { cin >> t; ans *= (t % mod); ans %= mod; } }
繰り返し二乗法
- 累乗の計算を高速に
- modも取りながら計算
- 参考:【競プロ】繰り返し二乗法と再帰関数 | なかけんの数学ノート
素数判定・テーブル作成
- 素数関連はコピペさせてもらうと早い
- 素数判定:素数判定(Is-Prime) | Luzhiled’s memo
- テーブル作成:素数テーブル(Prime-Table) | Luzhiled’s memo
フェルマーの小定理
- 競プロにおいて稀によく出てくる
- 参考1:フェルマーの小定理の証明と例題 | 高校数学の美しい物語
- 参考2:【競プロ】フェルマーの小定理 | なかけんの数学ノート
中国剰余定理
- 競プロにおいて稀によく出てくる
- 参考1:中国剰余定理の証明と例題(二元の場合) | 高校数学の美しい物語
- 参考2:中国剰余定理 カテゴリーの記事一覧 - けんちょんの競プロ精進記録
小技コード集
10進数の各桁の和
// 10進数の非負整数を渡すと、各桁の和が返ってくる int digits_sum(int x) { int sum = 0; while(x > 0) { sum += x % 10; x /= 10; } return sum; }
知っておくと良いこと
cin, cout
よりもscanf, printf
を使ったほうがおそらく速い- 普段から
long long
を使っておけば忘れずに済む #include <bits/stdc++.h>
は便利using namespace std;
は便利
勉強・参考になるウェブサイト
- けんちょんさんQiita:drken - Qiita
- けんちょんさんHatena:けんちょんの競プロ精進記録
- C++の勉強: C++入門 AtCoder Programming Guide for beginners (APG4b) - AtCoder
- 競プロライブラリ:Luzhiled’s memo | C++による競技プログラミングのライブラリです
- 競プロ数学:【競プロ】記事の一覧 | なかけんの数学ノート
- 競プロに役立つ話など:えびちゃんの日記
- かつっぱさんYouTube:かつっぱ競プロ - YouTube
- AtCoder YouTube:AtCoder Live - YouTube
競プロにはそこまで関係ないけど
競プロの書籍

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
- 作者:渡部 有隆
- 発売日: 2015/01/30
- メディア: Kindle版

最強最速アルゴリズマー養成講座 プログラミングコンテストTopCoder攻略ガイド
- 作者:高橋 直大
- 発売日: 2013/08/14
- メディア: Kindle版

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)
- 作者:大槻 兼資
- 発売日: 2020/10/02
- メディア: 単行本

世界で闘うプログラミング力を鍛える本 コーディング面接189問とその解法
- 作者:Gayle Laakmann McDowell
- 発売日: 2017/02/27
- メディア: Kindle版

リーダブルコード ―より良いコードを書くためのシンプルで実践的なテクニック (Theory in practice)
- 作者:Dustin Boswell,Trevor Foucher
- 発売日: 2012/06/23
- メディア: 単行本(ソフトカバー)
問題集
- ABC188 : D - Snuke Prime → 問題文の言い換え
- ABC188 : F - +1-1x2 → 考察&メモ化再帰
- ABC187 : A - Large Digits → 文字列操作
おわりに
やる気が続く限り、このページを更新していきたい。