はてなブックマーク

Binary Indexed Tree (またはフェニック木) は 数列 \(a_1, a_2, a_3, \cdots, a_n\) が与えられた時に、以下のようなことがそれぞれ \(O(log n)\) で実現できるデータ構造のことです。 i と x が与えられたとき、\(a_i \) に x を加算するi が与えられたとき、\(a_1 + a_2 + \cdots + a_i\) を求める ナイーブな方法では、1つ目に \(O(1)\)・2つ目に \(O(n)\) の計算量が必要です。 また、1から i 番目までの区間和を保存する方法では、1つ目に \(O(n)\)・2つ目に \(O(1)\) の計算量が必要となってしまいます。 BITの気持ち BITはセグメント木の機能を限定したようなもの セグメント木と呼ばれるデータ構造でも、Binary Indexed Tree の代替になるこ

ビットDPとは ビットDP(bit DP) とは、ビットで表現した集合を添え字に持つ動的計画法(DP)のことです。 基本的には、以下のような DPを考えます。 漸化式の更新式としては、 $$dp[ S \cup \{v\} ] = dp[ S ] + cost(S, v)$$ のように集合を1つずつ増やしていく形になることが多いです。 この集合に対するDPによって、\(n\) 個のものに対して\(n!\) 通りの順序の中から最適なものを計算するのを高速化できる場合があります。 集合をビットで表現する 実際には集合を配列の引数にするために、集合を2進数で表現します。全体集合 {0,1,2,…,n-1} の部分集合 S を n 桁の2進数で表現するのです。 例えば、全体集合 {0,1,2,…,9} の部分集合 {0,3,5} については、0bit目と3bit目と5bit目が 1で、それ以外が0

ビット全探索とは bit演算を上手く用いると、それぞれの要素に対して「使うか」「使わないか」の2通りがあるような、\(2^n\) 通りの場合を全探索することができます。 言い換えると、集合 \(\{0,1,2,3,…,n-1\}\) の部分集合を全て調べ上げることができます。 （ループ文を用いた全探索では、２重ループのときは \(n^2\) 通りの場合、3重ループのときは \(n^3\) 通りの場合を全て調べましたが、これでは指数通りの全探索は行うことができません。） ループ文を用いた全探索に比べると計算時間が爆発的に増えてしまうので、あまり大きな入力に対して行うとかなりの時間がかかってしまいます。余裕があれば実際にためして見ると良いでしょう。 (参考:計算量同士の比較と入力サイズによる比較) 具体例 \( \{4, 10, 1\}\) という3個の数字が与えられた時の選び方は、\(\{\

上の例では頂点1がまだ未探索なので、再び頂点1から深さ優先探索を始めれば良いです。その際は既に探索した頂点は探索しないようにしましょう。 計算量 幅優先探索：\(O(|V|+|E|)\)深さ優先探索：\(O(|V|+|E|)\) 未探索の頂点ごとに深さ優先探索や幅優先探索を行うので、計算量はどちらも \(O(|V|+|E|)\) となります。 C++での実装例 幅優先探索でのアルゴリズム グラフを受け取って、トポロジカルソートをした頂点のvectorを返す関数です。 #include <bits/stdc++.h> using namespace std; struct Edge { int to; }; using Graph = vector<vector<Edge>>; /* topo_sort(G): グラフG をトポロジカルソート 返り値: トポロジカルソートされた頂点番号 計算

※鋭意製作中 競技プログラミングで良く用いられるアルゴリズムやデータ構造のまとめです。 問題ごとの典型的な考え方については、競技プログラミングで解法を思いつくための典型的な考え方 を参考にして下さい。 初級編 全探索 「考えられる可能性を全て確かめて、最も良いものを探す」というやり方は、プログラミング特有の考え方です。これができるかどうかが、はじめの分かれ目になるでしょう。 ループによる全探索ビット全探索 (2^n 通り)順列(n!)の全探索DFSによる全探索（難しめ） その他にも工夫して全探索の探索数を減らす問題などがありますが、問題ごとに特有の性質を生かしていることがあります。 中級編 数学系 競技プログラミングでは数学的な知識も要求されます。 約数全列挙最大公約数・ユークリッドの互除法とその拡張最小公倍数素数判定素因数分解高速なべき乗の計算二項係数を素数で割った余りの計算「写像12相

競技プログラミングなどで頻出のテーマである組み合わせゲームやGrundy数についてまとめました。 前半は全ての方に向けての内容で、プログラム例や競技プログラミング特有の話題については後半にあります。 組み合わせゲームとは 組み合わせゲーム(Combinatorial games)とは以下のような特徴を持った二人で行うゲームのことを言います。 確定：ランダム性がない完全情報：全ての情報が全てのプレイヤーに公開されている 組み合わせゲームの例 以下のような多くのゲームが組み合わせゲームに分類されます。 オセロ将棋チェス囲碁Nim… これらのどれもが、二人で行うゲームで、確定であり完全情報でもあります。 特殊な組み合わせゲーム 組み合わせゲームの中でも特殊な性質を持つものは名前がついており、解析がしやすいものがいくつかあります。 二人零和有限確定完全情報ゲーム 組み合わせゲームに以下の性質がつい

競技プログラミングの問題を解くためには２つのステップがあります。 問題で要求されていることを言い換える知っているアルゴリズムやデータ構造を組み合わせて解く 必要な（知っておくべき）アルゴリズムやデータ構造は色々なところで学ぶことができます。 しかし、「問題の言い換え」や「アルゴリズムを思いつく」というのは、非常に様々なバリエーションがあり、問題をたくさん解かないとなかなか身につきません。 そこで、この記事は以下のことを言語化し、練習のための例題を提示することを目標とします。 問われていることを、計算しやすい同値なことに置き換える方法アルゴリズムを思いつくための考え方競技プログラミングで「典型的」と思われる考え方 ※一部問題のネタバレを含むので注意 ※良く用いられるアルゴリズムやデータ構造については競技プログラミングでの典型アルゴリズムとデータ構造 を参考にして下さい。 入力の大きさ(制約)

問題へのリンク 問題概要座標 \((0,0)\) からスタートして \(N\) 回の移動で \((X,Y)\) に到達する確率を求めたい。 1回の移動では、上下左右それぞれの方向に確率 \(\frac{1}{4}\ ...

セグメント木とは セグメント木とは、完全二分木（全ての葉の深さが等しい木）によって実装された、区間を扱うのに適したデータ構造のことです。 区間に対する操作を対数時間 O(log n) で行えることが特徴で、競技プログラミングなどで頻出となっています。 セグメント木でできること セグメント木は、区間に対する操作やクエリを行うことができます。 特に、 区間上の値を更新する任意の区間上の最小値や合計値などを取得する などが対数時間でそれぞれ行えるのが強みです。 区間上の合計値などは、累積和などを使えば前処理 O(N) ・クエリ O(1) で取得することもできます。しかし、区間上の値の更新と、合計値の取得が入り乱れるような時は、セグメント木の方が有効になることが多いです。 以下では説明のために、区間上の最小値 Range Minimam Query(RMQ) を扱うセグメント木を例として説明します