以下に、これまで管理者がコンテストで使用したり学んだりしたコードを、python3を中心に紹介します。

組み合わせ

組み合わせの列挙

サイコロの操作

サイコロの回転

最小公倍数・最大公約数

最大公約数を求めて、最小公倍数を求める

最長共通部分列問題(LCS: Longest Common Subsequence )

蟻本 p56 DP

最長増加部分列問題(LIS: Longest Increasing Subsequence)

蟻本 p64, 65 (bisect_left 使用) DP

辞書

辞書のソート

順列

順列の列挙

小数の操作

四捨五入

進数

進数の変換(整数)

スタックの利用

蟻本 P298 Largest Rectangle in a Histogram(POJ No.2559)

全探索

bit全探索

素因数分解

素因数分解

総和系

n 個の数列から異なる 2項を選んで作る積の総和

素数

素数の判定(試し割り法)

多項式

多項式の割り算

トポロジカルソート

トポロジカルソート

内外判定、当たり判定

2つの円の重なり判定
扇形に対する内外判定
線分の重なり判定
長方形の重なり判定
三角形と点の当たり判定

ナップサック問題

蟻本 p53 メモ化
蟻本 p55 DP
個数制限なし:蟻本 p58 DP

二次元配列

二次元配列の回転(シフト)

二次元配列の対角成分を抽出

二次元配列をらせん状に移動

二次元配列の列を抽出

二分探索(Binary Search)

蟻本 P26 「ハードルが上がった「くじびき」」

幅優先探索(BFS:Breadth-First Search)

蟻本 P37 「迷路の最短路」

bit演算

bit演算(正の整数)

ビットDP(bit DP)

蟻本 P173 「巡回セールスマン問題」

深さ優先探索(DFS: Depth-First Search)

蟻本 P35 「Lake Counting」

・競技プログラミングの鉄則 P353「Depth First Search」

部分和

部分和:蟻本 P34 深さ優先探索(DFS)

部分和:正の数列の部分和でSができるか?_動的計画法(DP)

個数制限付き部分和:蟻本 P63 動的計画法(DP)

分数

分数を約分して出力

方向の状態確認

どの方向を向いているか?(4方向)

無限大

無限大(INF)の作成

文字列

文字列 と 数値(ASCIIコード)を変換

文字列の置換 replace( )

文字列を任意の間隔でスライス

大文字 と 小文字を変換

・文字列探索(Knuth–Morris–Pratt algorithm、KMP法)

Monotonic Stack

Monotonic Stack

約数

約数の列挙

UnionFind(ユニオンファインド)

UnionFind

UnionFind で グラフの閉路(ループ)を検出する

リストの操作

文字列のリストを、大文字・小文字の区別をすることなくソート

リストの一括出力 .join( )

リストの先頭・末尾への要素の追加・削除

リストのソート

一次元配列のシフト(回転)

LeetCode

ListNode(もしくはLinked List)