いもす法とは 累積和の応用であり、ある区間に一定値を足す操作を複数回高速でするアルゴリズムである。 実装 let mut imos = vec![0; 2 * 10usize.pow(5) + 2]; for &(s, t, p) in &stp { imos[s] += p as isize; imos[t] -= p as isize; } let mut need = …

累積和とは Σ(i = n) ^ m のクエリを高速に解くためのアルゴリズムである。 事前にΣ(i = 0) ^ m を求めておいて、これをS_mとするとS_m - S_(n - 1)が求めたい総和になる。 事前に求めるパートがO(N)であり、それ以降はO(1)でクエリをこなすことができる。 …

二分探索とは ある条件Pを満たす集合と満たさない集合の境界値を求める問題で、その集合の境界面が一つしかないときに使える。（説明が下手） なんかこう数直線でこっから右がokでこっから左がngってなっているみたいな、、、、 まず、全体を二つに分けて、…

順列全列挙とは 集合Sの元からn個選ぶ順列に関して簡単に全探索する関数がある。 実装 for v in (Sのiterator).permutations(n) これによって探索できる。 組合せ全列挙とは 集合Sの元からn個組み合わせる方法に関して簡単に全探索する関数がある。 実装 for…

半分全列挙とは 普通に探索すると、nかかるような探索について特殊な状況だと √n log √nで探索が終わる方法がある。これを半分全列挙という。 bit全探索の半分全列挙 実装 let n1 = n / 2; let mut s1 = vec![]; let a1 = a[..n1].to_vec(); for v in 0usize…

bit全探索とは 集合の部分集合全体を探索するアルゴリズムをbit全探索という。 実装 for v in 0..1 << n { let is_in = (0..n).map(|i| (v >> i) & 1).collect::<Vec<_>>(); これによって集合 S = {0, 1, 2, ..., n - 1}の部分集合全体を探索できる。ここでループv</vec<_>…