はてなブックマーク

C++（ソートの補足） 複数の要素をまとめてソート 複数の要素をまとめてソートしたいときは、pairの配列（vector<pair<型1, 型2> >）を使うと簡単にできる。 #include <stdio.h> #include <vector> #include <algorithm> // sort #include <map> // pair using namespace std; int main() { int n = 10; vector<pair<int, int> > pairs(n); for (int i = 0; i < n; i++) { pairs[i] = make_pair(i*i % 10, i); } // firstが小さい順、secondが小さい順にソート sort(pairs.begin(), pairs.end()); for (int i =

動的計画法（ナップサック問題） 動的計画法とナップサック問題について解説します。 動的計画法とは 直接計算すると大きな時間がかかってしまう問題に対し、途中の計算結果をうまく再利用することで計算効率を上げる手法のこと。 「途中の計算結果を再利用」＝「同じ計算をしない」ということ 難しいように見えて考え方自体は単純 ICPC国内予選でもC問題～F問題くらいに何かしらの形で2,3題ほどでます 英語では「Dynamic Programming」と呼び、略して「DP」と呼ぶことが多いです。 動的計画法で効率的に解ける問題の一つに、ナップサック問題というものがあります。 ナップサック問題 ナップサック問題は、価値と重さが決まっている複数の品物を容量が一定のナップサックに詰め込むとき、ナップサックに詰め込める品物の価値の和の最大値は何であるか？　という問題です。 具体的には、以下の図のようになります。ナ

構文解析 再帰下降構文解析 構文解析にはいろいろな手法がありますが、プログラミングコンテストでは実装が単純かつそこそこ強力な（LL(1)文法を処理できる）再帰下降構文解析がよく使われます。 これは、関数の再帰を使って構文を小さな領域に分割していき、末端から値を確定させていく手法です。 四則演算の構文解析 例として、四則演算の構文解析を考えます。 ここでは四則演算は数字と括弧、+-*/の4つの演算子から成り立っているとします。演算子の優先順位も実際の四則演算の通り、掛け算と割り算が優先されます。ただし、全ての演算は整数だとします。以下は式の一例です。 まずは、四則演算の構文をBNF記法で表します。 BNF記法をあまり厳格に記述する必要はありませんが、演算子の優先順位はきっちり判別できるようにしておく必要があります。 最初に、式全体をexprという変数（非終端記号）で表すとします。 exprの

講習会資料 GitHub Pagesとjekyllで資料を作ってみた。 今後もこの形式で資料を用意するかは未定。今後資料を作るのかも未定。 目次 完全な目次はサークルWikiのページにあります。 C++ C++（標準ライブラリの紹介） C++（ソートの補足） 最短経路問題（ベルマンフォード法・ワーシャルフロイド法） 動的計画法（ナップサック問題） 幾何 構文解析 二分探索 最小全域木（クラスカル法とUnionFind）