sataniC++

C++、競プロ、数学などについて色々考えたりします。

アルゴリズム

ダブリング

「N個次の要素を知りたい」といった状況で頻繁に用いられるテクニックです。

Convex-Hull Trick

直線集合L={f_i(x)=a_ix+b_i}に対して、「Lへの直線f_k(x)=a_k x+b_kの追加」(以下、追加クエリ)と、「あるxに対し、Lの中で最小値(あるいは最大値)を取るような直線の値を求める」(以下、最小値クエリ)という2つのクエリを効率的に行うことが出来ます。

繰り返し自乗法

概要 の値を効率的に解きます。 使える状況 「をで割ったあまり」が欲しいときに、があまりにも大きいとその計算だけで時間がかかってしまうことがあります。そのような時には、この繰り返し自乗法を用いることで素早く求めることが出来ます。 説明 の値を求…

Imos法(いもす法)

累積和を用いて複数の要素の重なり・深さなどを計算します。

累積和手法

ある配列の任意の区間での部分和を求める。

二分法(二分探索)

ある条件を満たすものの最大値を求めます。 (ソートされた配列に対してある値を探索したいときも上記の方法で出来ます)