見出し画像
Photo by featurecompass

絶対にAtCoderで青コーダーになる！典型別 良問500選

rikimaru

はじめに

一部の地頭勢には「考察すれば同じ典型」と見なされてしまう問題であっても、私のような凡人には全く違う問題に見える事が良くあります。凡人にとっては、典型アルゴリズム・テクニックを細かく分類し覚えてしまった方が楽だと思っています。

このページの問題集は、私が青コーダーになるまでにかなり細かく典型アルゴリズム・テクニックを分類しまとめたもので、全部で約150典型、約500問約550問あります。

青コーダーを目指すのに知っていて損はないテクニックばかりです。レートが伸び悩んでいる方など、ぜひご活用ください。

※本記事で紹介する問題は随時アップデートします。詳細は変更履歴をご覧ください。


全探索

多重ループ全探索

愚直に組むとTLEする場合でも、工夫すれば計算量が収まる場合があります。

順列全探索

順列全探索は標準ライブラリで実装すると楽です。

bit全探索

2進数を上手く使って全探索します。

再帰全探索

再帰関数で実装します。慣れが必要です。

工夫した探索

二分探索

序盤で出会うアルゴリズムですが、応用範囲は広いです。

二分探索による中央値探索

二分探索は中央値の探索と相性が良いです。

二分探索による平均最大化

分子も分母も一定でないものを最大化する問題は二分探索で解ける事があります。

三分探索

グラフが下に凸の形で、平らな部分が最小値以外に存在しない場合に使えます。

尺取り法

慣れるまではバグらせやすいので多めに練習したいです。

半分全列挙

半分に分けて全列挙すると間に合う事があります。

ソートに関する問題

転倒数

バブルソートする時のスワップ回数です。

2数列ペア積の最大値を最小化

同じ長さの数列A、Bがあり、それぞれ要素の順番を並べ替えて良いとき、max_i ( A[i] * B[i] )を最小化する為にはAを昇順、Bを降順に並べると良いです。

ペアつなぎ長

数列Aと数列Bの各要素をつなぐとき、その長さ（差の絶対値）の総和を最小にする問題です。

区間の問題

累積和

累積和の特徴を使って解く問題があります。

2次元累積和

2次元でも累積和が使えます。

いもす法

複数の区間加算を一括して求める時に活躍します。

連続部分列問題

連続部分列に対して愚直に計算するとTLEする場合、まとめて処理する事が求められます。

Mo's algorithm

区間クエリが先読みできる場合、計算量を抑えられる面白いアルゴリズムです。

区間max値の総和

降順か昇順で考えてみると見通しが良くなります。

最短経路問題

BFS

最短経路と言えばBFSです。ダイクストラも同様ですが、始点が複数あっても良いです。

01-BFS

辺のコストが0と1しかない場合のBFSです。計算量にlogがつかないのでダイクストラより高速に動作します。

ダイクストラ法（Dijkstra's algorithm）

言わずと知れたダイクストラ法です。

拡張ダイクストラ法（Extended Dijkstra's algorithm）

頂点とその他何かの状態を組み合わせたものを拡張した頂点（あるいは状態）と見なしてダイクストラします。BFSでも同様です。

ポテンシャル法

経路によらず決まる値（位置エネルギーのようなもの）をポテンシャルとすると、ポテンシャルの変化は経路と切り離して考えることができます。

ワーシャルフロイド法（Warshall-Floyd algorithm）

全点間の最短距離がO(N^3)で求まる面白いアルゴリズムです。負辺があっても使え、実装も軽いです。

ベルマンフォード法（Bellman-Ford algorithm）

負辺ありでも使え、負閉路検出にも使えるベルマンフォード法です。

一度に複数辺を進めると考える最短経路

一度に複数辺を進めると考えると見通しが良くなる問題です。

最短経路問題＋α

最短経路問題に追加して何かを求めさせたり、何か工夫しないと解けない問題です。

グラフに関する問題

木と森

木や森の性質を利用する事で解ける問題があります。

木の直径・重心

直径・重心の性質を知らないと解きにくい問題です。

オイラーツアー（Euler tour）と部分木

オイラーツアーする事で部分木を区間で表現する事ができます。

LCA 最小共通祖先（Lowest Common Ancestor）

覚えておいて損はしないテクニックです。

完全二分木

完全二分木の特殊な構造を上手く利用して解きます。

木の次数列

全頂点の次数が1以上かつ次数の合計が2*(N-1)であれば木を構成できます。

MST 最小全域木（Minimum Spanning Tree）

クラスカル法が有名です。

全域木の構成

木でない連結なグラフから全域木を構成する問題です。また、全域木を考える事で見通しが良くなる問題もあります。

なもりグラフ（pseudo tree）とfunctional graph

functional graphは必ずなもりグラフ（連結成分数が1とは限らない）の形になります。

スターグラフ（うにグラフ）

特殊な構造をしています。

DAG（サイクルのない有向グラフ）とトポロジカルソート

DAGであればトポロジカルソート可能です。また、計算順序が定まるという事になるので、DAG上でDPする事もできます。

サイクル検出

グラフのサイクル検出です。有向グラフならSCC（強連結成分分解）で殴れる事があります。また、ダブリングで楽に解ける問題もあります。

ダブリング（Doubling）

functional graph上である頂点からK回進んだ頂点がO(log(K))で求められます。

SCC 強連結成分分解（Strongly Connected Components）

SCCするとトポロジカルソートされたDAGになります。

最小クリーク被覆問題

与えられたグラフが最小何個のクリーク（完全グラフ）に分割できるかという問題です。この問題を通して、完全グラフ判定、部分集合全列挙もついでに学べます。

2部グラフ

2部グラフには綺麗な性質が幾つもあります。

超頂点を設ける

超頂点を設定する事で解決できる問題があります。

橋・関節点（Bridge/Articulation points）

low-link法が有名です。

データ構造

Union-Find tree/Disjoint set union

マージや連結判定が高速に行えるデータ構造です。重み付きもあります。

集合（set）・連想配列（map/dict）・優先度付きキュー（priority que/heap）

標準ライブラリで整備されている事が多いですが、これらを上手く使うことで計算量を抑えられる問題です。

双方向リスト（単方向・双方向）

要素の前後関係のみ保持するリストです。ランダムアクセスは苦手ですが、要素の挿入・削除がO(1)でできます。

小さい方からK個の和

与えられた要素に対し、小さい方からK個の和を管理します。

括弧列

括弧列はデータ構造の名前ではありませんが、データの持ち方に特徴があります。

BIT/Fenwick tree

一点加算・区間和取得（区間加算・一点取得）ができます。

セグメント木（Segment tree）

モノイドであれば何でも乗せられます。

遅延伝播セグメント木（Lazy propagation segment tree）

区間更新もできるセグメント木です。

永続データ構造

永続データ構造の雰囲気を感じられる良問を紹介します。

Sparse Table

区間の取り方を理解する良問があります。

DP（動的計画法）

部分和問題

部分和問題はDPの基本です。

ナップサックDP

こちらもDPの基本です。

経路数問題

経路数はDPとの相性が良いです。

bit DP

頻出のbit DPです。制約からbit DPを使うはずと見抜ける事が殆どです。

部分集合の部分集合DP

bit DPをする際、ある部分集合からその部分集合全てに遷移する場合のDPです。このテクニックは最小クリーク被覆問題でも出てきました。

耳DP

どの区間まで進んだかを状態に持つ自然なDPですが、名前が特殊なのでカテゴリーとして追加しました。

LCS 最長共通部分列（Longest Common Subsequence）

LCSの求め方は典型中の典型ですが、同じ考え方を利用した問題もあります。

文字列の部分列

文字列Sが文字列Tの（連続とは限らない）部分列となっているかの判定法及びその性質を利用した問題です。

LIS 最長増加部分列（Longest Increasing Subsequence）

大きく分けて2種類の実装がありますが、いずれも他のDPとは実装の毛色が異なります。

桁DP

桁ごとに考えていく場合のDPです。ある数字未満になる事が確定したかどうかで状態を分けるところに特徴があります。

対戦ゲームDP

ゲーム終了状態から逆に考えていくと順次求まります。

円環DP

円環になっており始点をどのように決めるか自明でない時のDPです。

木DP

根付き木を考え、頂点ごとに部分木に対する情報を保持するDPです。

全方位木DP（Rerooting）

全頂点について、ある頂点を根付き木とした場合の何らかの値を求めるDPです。

区間DP

区間[l,r)での最適値や場合の数を考えたい時に使えます。数列から隣り合う要素をくっつける、あるいは切り取る操作をする場合に使える事が多い印象があります。

DP復元

遷移元を記録しておくか、逆順に辿ります。

DP高速化

累積和やセグメント木などを用いてDPの遷移を高速化するテクニックです。

長さを持つDP

要素番号だけでなく操作回数などの長さも状態に持つDPです。

ひねりDP

DPで持つ情報や遷移を工夫する事で解ける問題です。

前処理DP

前処理する事でDPできる形に持っていく問題です。

DP in DP

あるDPの結果を状態として持ちながらDPしていきます。

インラインDP

同じテーブルを使いまわすDPです。

戻すDP

途中の操作を無かったことにする（＝戻す）DPです。

挿入DP

順列を決める時に使えます。

決め打ちDP

ある不確定な条件を決め打つ事によりDPできる場合があります。

Top2を持つ

ある変数に関する状態が本質的に2つしか必要ない場合、DPの添え字ではなく最善値（=DPの値）としてTop2を保持するテクニックです。

文字列

ローリングハッシュ（Rolling hash）

文字列の一致判定で汎用性高く使えます。

LCP 最長共通接頭辞（Longest Common Prefix）

Trie木が有名です。ローリングハッシュで殴れる場合も多いです。

Zアルゴリズム

各文字について、先頭から何文字一致するかをO(N)で求める事ができます。

区間反転操作

区間に対する何かしらの操作である場合、両端のみ変化すると考える事で考察が進む場合があります。

Suffix Array

ある文字列の全接尾辞を辞書順に並べた配列を求めるアルゴリズムです。

数

XOR

XORは扱いやすい性質が多く頻出です。

OR

ORも稀に出題されるようです。

2進数

お馴染みの2進数です。

MEX

使われていない最小の非負整数です。慣れていないと難しいです。

整数とMOD

切上切捨除算、等差・等比数列、MODの逆元、フェルマーの小定理あたりを押さえておきたいです。

約数

約数の数は多くないです。

GCD 最大公約数と拡張ユークリッドの互除法

趣深いです。

LCM 最小公倍数

LCMの性質を利用して解く問題もあります。

素因数分解

素因数分解はO(sqrt(M))でできます。

エラトステネスの篩（Sieve of Eratosthenes）と高速素因数分解

エラトステネスの篩でN以下の素数をO(N loglogN)で全列挙できます。また、篩の持ち方を工夫する事で高速に素因数分解する事ができます。

平方数

一度見るとなるほどという感じです。

剰余埋めつくし

a,2a,3a,…をNで割った余りで埋めていくと、gcd(a,N)の倍数が全て埋まりそれ以外の数は埋まりません。

約数系包除

約数・倍数の関係にある数について重複して数えてしまう設定の問題です。

CRT 中国剰余定理（Chinese Remainder Theorem）

名前にインパクトがあります。

小数

小数の演算には誤差がつきまといます。

最小桁和

難しいですが、どこかで役に立つ考え方かもしれません。

場合の数と確率・期待値

組合せ

組合せの数を数え上げます。

Lucasの定理

mod m（mは小さい）でnCrを求めたい時に使えます。

包除原理

数え上げ問題で使える時があります。

分布に対するDP

分布に対して1つずつ決めていく事で現実的な計算量でDPできる事があります。

独立事象を掛け合わせる

独立に考えられるものは掛け合わせると良いです。

期待値

期待値も重要なテーマです。

期待値の線形性

E[X+Y] = E[X] + E[Y]が成り立ちます。

対称性を利用する

対象なものはまとめて計算する事ができます。

2変数問題

平面走査

xで昇順（あるいは降順）ソートして順番に処理する事で、着目すべき変数をyのみに減らすテクニックです。

XY独立に考える

平面の問題であっても、XY独立に考える事ができる場合があります。

変数分離

変数を分離する事で見通しが良くなる問題です。

十字領域

2次元マス上から十字領域を選び計算させる問題です。

貪欲法

区間スケジューリング問題

思いつくのが難しい貪欲法ですが、覚えてしまえば勝ちです。

区間貪欲

区間スケジューリングでなくても、区間の問題は貪欲法で解く場合があります。

その他貪欲法

貪欲法のバリエーションは多いです。

行列

行列積・行列累乗

漸化式を行列の積と捉えると上手くいく事があります。

アフィン変換

アフィン変換は同次変換行列の積で表現できます。

掃き出し法

大学1年生の線形代数で序盤に習う掃き出し法です。

その他典型テクニック

カテゴリ分けが難しいものの押さえておきたい典型テクニックを列挙します。

主客転倒

Σの順番を入れ替えるなど、固定するものの視点を変えてみると上手く計算量が抑えられる事があります。

投票方式で考える

各要素ごと寄与するものに投票していく事で、最善値を求める事ができます。

時系列順に処理する

同じ条件のものをまとめて処理する事で計算量が抑えられます。

後ろから考える

どういう時に後ろから考えると良いのかまで言語化できれば完璧です。

三つ組は真ん中を固定

真ん中を固定すると左側と右側を考えやすくなります。

マンハッタン距離・チェビシェフ距離

幾つか面白い性質があります。45度回転とも関係が深いです。

調和級数や√Nで計算量を落とす

一見すると間に合わない計算量でも、調和級数や√Nで区切ったりすると間に合う問題です。

データ構造をマージする一般的なテク

単純に要素をマージすると計算量が壊れますが、少しの工夫で計算量が抑えられます。

標準形を考える

標準形を考える事で本質的に同じ情報を1つにまとめる事ができます。

差分を考える

何かが1つ変化した時の差分を考える事で、計算量を減らせる事があります。

K番目を答える

単純なようで難しいです。

偶奇に注目する

偶奇を考える事で見通しが良くなる問題です。

円環問題

そのままでは扱いにくいので、直線に並べ替えてみると見通しが良くなる事があります。

不変量を見つける

不変量を上手く見つける事で解ける問題です。

ある要素が必ず含まれるか（or含まれる事があるかどうか）の判定

左右から攻めてその要素の必要性に帰着できると良いです。

クエリ先読み

先読みする事で解ける問題です。

ハッシュで一致判定

一致判定にはハッシュが便利です。

Nimとgrundy数

知っておいて損はないと思います。

鳩の巣原理

一度聞いたら忘れない名前です。

最終形を考える

操作が終わった時の状態から考えると考察が進む場合があります。

max(max())の形に帰着させる

この形に持ち込めれば、ソートなどのテクニックによって簡単に解が求まります。

置換（巡回置換・偶置換/奇置換）

大学1年生の線形代数で唐突に現れ、みな混乱する置換です。

パスカルの三角形

不思議な性質が沢山あります。

操作列を考える

操作列を考えると見通しが良くなる場合があります。

関数の形のまま考える

関数の形のまま合成していく事ができる場合があります。

E - Filters

ヒストグラム最大長方形（スタック利用）

ヒストグラム内で最大面積の長方形を求める問題（及び類似する問題）です。O(N)で求めるテクニックを覚えておきたいです。

階段状にかさ増しする

各値が相異なる必要がある場合など、事前にindex値分だけかさ増しするテクです。

偏角ソート

普通のソートですが名前が付いています。誤差なしでソートする事もできるようです。

平方分割

平方で分割して計算量を抑えるテクです。

最大と最小の差を最小化

なるべく小さな範囲に収めるという事です。

挿入ソート

ちょっとした発想が必要ですが、解法が面白いです。

牛ゲー

牛ゲーの名前の由来が解説動画の中で説明されています。

最大フロー・最小カット

色々な実装方法があるらしいですが、ACLにも入っています。

整数計画問題（線形計画問題）を工夫して解く

ナップサック問題など一般にNP困難ですが、DPでも解けない場合は制約などに注目し工夫すると解ける場合があります。

木を見て森を見る

全体を見ると難しくても、局所を見るだけで大丈夫な場合があります。

周期に着目する

周期が分かればシミュレーションしなくてもO(1)で求まります。

構築系問題

条件を満たす数列などを構築させる問題です。

実装系問題

アルゴリズム的な工夫より実装そのものを問われる問題です。

変更履歴


いいなと思ったら応援しよう！