二分探索
二分探索とは
ある条件Pを満たす集合と満たさない集合の境界値を求める問題で、その集合の境界面が一つしかないときに使える。（説明が下手）
なんかこう数直線でこっから右がokでこっから左がngってなっているみたいな、、、、
まず、全体を二つに分けて、するとそのどっちかはokかngだけの集合となっているので、それをmidにして、、、、なんかまとめる必要ないですね。自分ではわかっているのでリクエストがあれば頑張って言語化します。
実装
let mut ok = n as isize;
let mut ng = -1;
while ok - ng > 1 {
let mid = (ok + ng) / 2;
if a[mid as usize] >= k {
ok = mid;
} else {
ng = mid;
}
}
これはokの集合が右側にある時ですね！
順列全列挙、組合せ全列挙
順列全列挙とは
集合Sの元からn個選ぶ順列に関して簡単に全探索する関数がある。
実装
for v in (Sのiterator).permutations(n)
これによって探索できる。
組合せ全列挙とは
集合Sの元からn個組み合わせる方法に関して簡単に全探索する関数がある。
実装
for v in (Sのiterator).combinations(n)
これによって探索できる。
半分全列挙
半分全列挙とは
普通に探索すると、nかかるような探索について特殊な状況だと √n log √nで探索が終わる方法がある。これを半分全列挙という。
bit全探索の半分全列挙
実装
let n1 = n / 2;
let mut s1 = vec![];
let a1 = a[..n1].to_vec();
for v in 0usize..1 << n1 {
let ok = (0..n1).map(|i| (v >> i) & 1)
.collect::<Vec<_>>();
let mut tot = 0;
for i in 0.. n1 {
if ok[i] == 1 {
tot += a1[i];
}
}
s1.push(tot);
}
let n2 = n - n1;
let mut s2 = vec![];
let a2 = a[n1..].to_vec();
for v in 0usize..1 << n2 {
let ok = (0..n2).map(|i| (v >> i) & 1)
.collect::<Vec<_>>();
let mut tot = 0;
for i in 0..n2 {
if ok[i] == 1 {
tot += a2[i];
}
}
s2.push(tot);
}
s2.sort();
let mut ans = 0;
for &s1 in &s1 {
if s1 > t {
continue;
}
let upper = t - s1;
let mut ok = -1;
let mut ng = 1 << n2 as isize;
while ng - ok > 1 {
let mid = (ok + ng) / 2;
if s2[mid as usize] <= upper {
ok = mid;
} else {
ng = mid;
}
}
if ok == -1 {
ans = ans.max(s1);
} else {
ans = ans.max(s1 + s2[ok as usize]);
}
}
解説
まず集合の元を2つに分ける。そして2つの組に対してその分けた集合でどのような合計が作れるかをみる。 その後、1つの組に対してループを回しながら、残り1つの組に対して二分探索で答えを探している。
n4ループの半分全列挙
解説
これはn2のループずつで見た時の答えをメモして、残りを二分探索で求める方法である。この問題に出会ってないから実装は無し。
深さ優先探索（DFS）
深さ優先探索とは
グラフにおいて、いけるところまで深くいき、いけなくなったら引き返してまた同じことをする探索を深さ優先探索という。
実装
実装方法として再帰関数を用いる方法とstackを用いる方法がある。 再帰関数を使う方法は逃げてなのでstackでやるようにしている。
let mut q = vec![];
q.push(s);
let mut used = vec![vec![false; w]; h];
while let Some((x, y)) = q.pop() {
for &(dx, dy) in [(1, 0), (0, 1), (!0, 0), (0, !0)].iter() {
let x = x.wrapping_add(dx);
let y = y.wrapping_add(dy);
if x < h && y < w && !used[x][y] && c[x][y] == b'.' {
q.push((x, y));
used[x][y] = true;
}
if x < h && y < w && c[x][y] == b'g' {
println!("Yes");
return;
}
}
}
これは実装例であるので他の問題は自分で頑張ろう。
幅優先探索（BFS）
幅優先探索とは
グラフにおいて、ある頂点から初めてそこからの最短距離が短い順にグラフの頂点を探索する方法である。
実装
これはVecDequeを用いて実現できる。これは前後から取り出しができるvectorである。
let mut q = std::collections::VecDeque::new();
let mut used = vec![false; n];
q.push_back(0);
while let Some(i) = q.pop_front() {
// ここに取り出した頂点iに対して行いたい処理を書く
for &j in &e[i] {
if !used[j] {
q.push_back(j);
}
}
}
となる。
強連結成分分解
すみません。人からライブラリを拝借して一旦終わります。 理解できないですこれ。
// ---------- begin scc ----------
pub fn strongly_connected_components<G, I>(size: usize, graph: G) -> (usize, Vec<usize>)
where
G: Fn(usize) -> I,
I: Iterator<Item = usize>,
{
let mut ord = vec![0; size];
let mut res = vec![0; size];
let mut vertex = vec![];
let mut dfs = vec![];
let mut id = 0;
for s in 0..size {
if ord[s] > 0 {
continue;
}
vertex.push(s);
ord[s] = vertex.len();
dfs.push((s, graph(s)));
while let Some((v, mut it)) = dfs.pop() {
(|| {
while let Some(u) = it.next() {
if ord[u] == 0 {
vertex.push(u);
ord[u] = vertex.len();
dfs.push((v, it));
dfs.push((u, graph(u)));
return;
}
}
let low = graph(v).map(|u| ord[u]).min().unwrap_or(ord[v]);
if low < ord[v] {
ord[v] = low;
return;
}
while let Some(u) = vertex.pop() {
ord[u] = !0;
res[u] = id;
if u == v {
break;
}
}
id += 1;
})();
}
}
res.iter_mut().for_each(|p| *p = id - 1 - *p);
(id, res)
}
// ---------- end scc ----------
// ---------- begin CSR ----------
pub struct CSR {
size: usize,
pos: Vec<u32>,
elist: Vec<u32>,
}
impl CSR {
pub fn new<I>(size: usize, it: I) -> Self
where
I: Iterator<Item = (usize, usize)> + Clone,
{
let mut pos = vec![0; size + 1];
for (s, t) in it.clone() {
assert!(s < size && t < size);
pos[s + 1] += 1;
}
for i in 1..=size {
pos[i] += pos[i - 1];
}
let mut x = pos[..size].to_vec();
let mut elist = vec![0; pos[size] as usize];
for (s, t) in it {
let x = &mut x[s];
elist[*x as usize] = t as u32;
*x += 1;
}
CSR { size, pos, elist }
}
pub fn list(&self, v: usize) -> impl Iterator<Item = usize> + '_ {
assert!(v < self.size);
let s = self.pos[v] as usize;
let t = self.pos[v + 1] as usize;
self.elist[s..t].iter().map(|p| *p as usize)
}
}
// ---------- end CSR ----------
使用例
fn main() {
input! {
n: usize,
m: usize,
e: [(u32, u32); m],
}
let graph = CSR::new(n, e.iter().map(|e| (e.0 as usize, e.1 as usize)));
let (len, id) = strongly_connected_components(n, |v| graph.list(v));
let csr = CSR::new(n, id.iter().enumerate().map(|(v, k)| (*k, v)));
println!("{}", len);
for i in 0..len {
let len = csr.list(i).count();
println!("{} {}", len, csr.list(i).join(" "));
}
}
