競技プログラミングでの典型アルゴリズムとデータ構造

2020年3月1日

※鋭意製作中

競技プログラミングで良く用いられるアルゴリズムやデータ構造のまとめです。

問題ごとの典型的な考え方については、競技プログラミングで解法を思いつくための典型的な考え方 を参考にして下さい。

初級編

全探索

「考えられる可能性を全て確かめて、最も良いものを探す」というやり方は、プログラミング特有の考え方です。これができるかどうかが、はじめの分かれ目になるでしょう。

その他にも工夫して全探索の探索数を減らす問題などがありますが、問題ごとに特有の性質を生かしていることがあります。

中級編

数学系

競技プログラミングでは数学的な知識も要求されます。

動的計画法

動的計画法の問題は種類も多く、慣れが必要です。

グラフ

木

データ構造

C++ の標準ライブラリで提供されているデータ構造以外に、自分で実装する必要のあるものがあります。

その他・テクニック

上級編

フロー

木

データ構造

文字列系

その他・テクニック