2020年5月19日その他二次元, 座標圧縮

座標圧縮は、座標の情報から、位置関係や大小関係だけ抽出するテクニックです。

仮に座標の範囲が非常に広い場合、以下のような不都合が生じてしまいます。

例:\(0\) ~ \(10^9\) の数直線はメモリにのらない

その他, その他競プロ, LCA, ダブリング, 繰り返し二乗法

ダブリングは、全体の要素数がN個あって1回移動した時にどの要素に到達するのか定まっているとき、「K個先の要素を求めるのに \(O(K)\) かかる」ような状況において

前処理:\(O(N \log K)\) 時間, \(O(N ...

その他圧縮, 復元, ランレングス圧縮

ランレングス圧縮(ランレングス符号化)とは、データの圧縮方法の一つで、圧縮前に正確に復元することができる可逆圧縮の一種です。

同じ文字が連続して何文字出現するかに変換します。

例:

In: aaal ...

2020年3月20日その他区間和, 区間, 累積和, 配列

要素数 N の数列 \(\{a_0, a_1, a_2, \cdots, a_{N-1}\}\) が与えられた時に、区間

累積和の気持ち累積和とは

累積和は、「始めから i 番目までの和を前処理で計算したもの」です

2020年3月20日その他

大きさが \(H × W\) の二次元配列 \(a\) 上において、 + a + … + a
+ a + a + … + a
+ …
+ a + a + … + ...

2020年3月15日その他bit全探索, 全探索, テーマ記事, 競プロ, 半分全列挙, テクニック

N 個の要素の組み合わせを計算する際、N/2 ずつの2グループに分けてそれぞれを全列挙し、組み合わせ方を高速に求めるという工夫を「半分全列挙」と言います。

選択した数列の合計値を半分全列挙で探索する場合(\(2^4\)ずつに分け ...

2020年3月13日その他テーマ記事, 競プロ, ゲーム, 二人零和有限確定完全情報ゲーム, Grundy数, 不偏ゲーム, 組み合わせゲーム, スプレイグ・グランディの定理, Nim, NimK, Misere Nim

競技プログラミングなどで頻出のテーマである組み合わせゲームやGrundy数についてまとめました。

前半は全ての方に向けての内容で、プログラム例や競技プログラミング特有の話題については後半にあります。

組み合わせゲーム ...

2020年3月6日その他区間和, テーマ記事, 競プロ, 区間, 累積和, imos法, 二次元区間和

区間の更新がない場合

区間の更新が生じない場合は、累積和を用いることで高速にクエリを処理できます。

一次元の区間和

累積和を用いることで、

前処理:\(O(N)\)
クエリ:\(O(1)\)

で処理がで ...