CodeForces 402 div2

http://codeforces.com/contest/779
A
特に
B
サイズ小さいから全列挙したんだけど普通に後ろから０以外の数字数えるだけでいいじゃん……
アホか……
C
差を取ってソートして貪欲。蟻本の初級編とかに載ってそう。
D
二分探索。
いかにも判定問題に帰着すると簡単っぽいのに、文字列特有のことをするんじゃないかと思って時間を無駄にした。
無駄にソートしてるからlog二回つくけどこどふぉのサーバーは速いので余裕。

fn exec() {
    let mut sc = Scanner::new();
    let s: Vec<u8> = sc.ne::<String>().into_bytes();
    let t: Vec<u8> = sc.ne::<String>().into_bytes();
    let n = s.len();
    let a: Vec<usize> = (0..n).map(|_| sc.ne()).collect();
    fn ok(s: &Vec<u8>, t: &Vec<u8>) -> bool {
        let n = s.len();
        let m = t.len();
        let mut tid = 0;
        for i in 0..n {
            if s[i] == t[tid] {
                tid += 1;
                if tid == m {
                    return true;
                }
            }
        }
        false
    }
    let m = t.len();
    let (mut l, mut r) = ((m - 1) as i32, n as i32);
    while r - l > 1 {
        let mid = (r + l) / 2;
        let from = n - mid as usize;
        let mut p = a[from..n].to_owned();
        p.sort();
        let mut q = vec![0u8; p.len()];
        for i in 0..p.len() {
            q[i] = s[p[i] - 1];
        }
        if ok(&q, &t) {
            r = mid;
        } else {
            l = mid;
        }
    }
    println!("{}", n - r as usize);
}

E
トポロジカルソートしてビットごとに全部試すだけなんだけど実装遅いしライブラリなかったからダメだった。
無駄に丁寧に書いてるとはいえ、さすがに実装多すぎじゃない？

use std::collections::BTreeMap;
fn exec() {
    let mut sc = Scanner::new();
    let n: usize = sc.ne();
    let m: usize = sc.ne();
    let mut name = BTreeMap::new();
    enum Ope {
        Or,
        Xor,
        And,
    }
    enum Val {
        Def(Vec<u8>),
        Not((Ope, usize, usize)),
    }
    let mut input = vec![Vec::new(); n];
    for i in 0..n {
        let s: String = sc.ne();
        name.insert(s.into_bytes(), i);
        let _ = sc.ne::<String>();
        let t: Vec<u8> = sc.ne::<String>().into_bytes();
        let t0 = t[0];
        input[i].push(t);
        match t0 {
            b'0' | b'1' => {}
            _ => {
                let t: Vec<u8> = sc.ne::<String>().into_bytes();
                input[i].push(t);
                let t: Vec<u8> = sc.ne::<String>().into_bytes();
                input[i].push(t);
            }
        }
    }
    let mut val = Vec::new();
    let mut adj = vec![Vec::new(); n];
    let inf: usize = 1000000000;
    for i in 0..n {
        if input[i].len() == 1 {
            val.push(Val::Def(input[i][0].clone()));
        } else {
            let j = match input[i][0][0] {
                b'?' => inf,
                _ => *name.get(&input[i][0]).unwrap(),
            };
            let k = match input[i][1][0] {
                b'X' => Ope::Xor,
                b'O' => Ope::Or,
                _ => Ope::And,
            };
            let l = match input[i][2][0] {
                b'?' => inf,
                _ => *name.get(&input[i][2]).unwrap(),
            };
            val.push(Val::Not((k, j, l)));
            if j != inf {
                adj[j].push(i);
            }
            if l != inf && j != l {
                adj[l].push(i);
            }
        }
    }
    let ord = topological(&adj).unwrap();
    let mut ansmin = vec![0; m];
    let mut ansmax = vec![0; m];
    for j in 0..m {
        let mut score = vec![0; 2];
        for k in 0..2 {
            let mut flag = vec![0; n];
            for i in 0..n {
                let v = ord[i];
                flag[v] = match val[v] {
                    Val::Def(ref x) => if x[j] == b'1' { 1 } else { 0 },
                    Val::Not(ref x) => {
                        let a = match x.1 {
                            num if num == inf => k,
                            _ => flag[x.1],
                        };
                        let b = match x.2 {
                            num if num == inf => k,
                            _ => flag[x.2],
                        };
                        match x.0 {
                            Ope::And => a & b,
                            Ope::Or => a | b,
                            Ope::Xor => a ^ b,
                        }
                    }
                };
            }
            score[k] = flag.iter().sum();
        }
        if score[0] > score[1] {
            ansmin[j] = 1;
        } else if score[0] < score[1] {
            ansmax[j] = 1;
        }
    }
    for i in 0..m {
        print!("{}", ansmin[i]);
    }
    println!("");
    for i in 0..m {
        print!("{}", ansmax[i]);
    }
    println!("");
}

fn topological(adj: &Vec<Vec<usize>>) -> Option<Vec<usize>> {
    let n = adj.len();
    let mut deg = vec![0; n];
    for i in 0..n {
        for &nxt in &adj[i] {
            deg[nxt] += 1;
        }
    }
    let mut ord = Vec::new();
    for v in 0..n {
        if deg[v] == 0 {
            ord.push(v);
        }
    }
    for h in 0..n {
        if h >= ord.len() {
            return None;
        }
        let v = ord[h];
        for &nxt in &adj[v] {
            deg[nxt] -= 1;
            if deg[nxt] == 0 {
                ord.push(nxt);
            }
        }
    }
    Some(ord)
}

今日の反省点はやっぱり実装が遅いことだけど二日酔いなので仕方ない気もする。
Eはワーシャルフロイドみたくやったほうが早く書けるんかな。

[追記]
F:
なんと愚直にマージするだけで解けるらしい。

fn exec() {
    let mut sc = Scanner::new();
    let n: usize = sc.ne();
    let mut adj = vec![Vec::new(); n];
    let mut edge = vec![Vec::new(); n];
    for _ in 0..n - 1 {
        let u = sc.ne::<usize>() - 1;
        let v = sc.ne::<usize>() - 1;
        adj[u].push(v);
        adj[v].push(u);
        let s: Vec<u8> = sc.ne::<String>().into_bytes();
        let c = (s[0] - b'a') as usize;
        edge[u].push((v, c));
        edge[v].push((u, c));
    }
    let (t_ord, t_par) = get_tree_ord(&adj, 0);
    let t_size = {
        let mut res = vec![1; n];
        for i in (1..n).rev() {
            let cur = t_ord[i];
            let par = t_par[cur];
            res[par] += res[cur];
        }
        res
    };
    let (t_depth, max_depth) = {
        let mut res = vec![0; n];
        let mut ma = 0;
        for i in 1..n {
            let cur = t_ord[i];
            let par = t_par[cur];
            res[cur] = res[par] + 1;
            ma = max(ma, res[cur]);
        }
        (res, ma)
    };
    fn merge(nodes: Vec<usize>,
             edge: &Vec<Vec<(usize, usize)>>,
             t_par: &Vec<usize>,
             t_size: &Vec<usize>)
             -> usize {
        if nodes.len() == 1 {
            return t_size[nodes[0]];
        }
        let mut merged = vec![Vec::new(); 26];
        for &cur in &nodes {
            for nxt in &edge[cur] {
                if nxt.0 == t_par[cur] {
                    continue;
                }
                merged[nxt.1].push(nxt.0);
            }
        }
        let mut res = 1;
        for vec in merged {
            if vec.is_empty() == false {
                res += merge(vec, &edge, &t_par, &t_size);
            }
        }
        res
    }
    let mut saved = vec![0; max_depth + 1];
    for i in 0..n {
        let cur = t_ord[i];
        if adj[cur].is_empty() {
            continue;
        }
        let arg: Vec<_> = adj[cur].iter().filter(|&&x| x != t_par[cur]).cloned().collect();
        let res = merge(arg, &edge, &t_par, &t_size);
        saved[t_depth[cur]] += t_size[cur] - res;
    }
    let ma = *saved.iter().max().unwrap();
    let pos = saved.iter().position(|&x| x == ma).unwrap();
    println!("{}\n{}", n - ma, pos + 1);
}

fn get_tree_ord(adj: &Vec<Vec<usize>>, root: usize) -> (Vec<usize>, Vec<usize>) {
    let n = adj.len();
    let inf = 1000000000;
    let mut par = vec![inf; n];
    let mut ord = Vec::new();
    let mut stack = Vec::new();
    stack.push(root);
    while let Some(cur) = stack.pop() {
        ord.push(cur);
        for &nxt in &adj[cur] {
            if par[nxt] == inf && nxt != root {
                par[nxt] = cur;
                stack.push(nxt);
            }
        }
    }
    (ord, par)
}

やってることは「あるノードを消したときの操作を愚直にシュミレーションする」というだけで、一見N ^ 2かかりそうに見える。
ところがマージ操作において

        if nodes.len() == 1 {
            return t_size[nodes[0]];
        }

とできるのが意外と本質的な枝刈りになってるっぽい。
枝刈りがないときの最大ケースは

o
|
o
|
o
|
o

みたいな木でN。全ノードに対してN。
枝刈りがあるときの（あるノードに対しての）最悪ケースは

     o
     |
   a|-b|
    o  o
   e| e| 
    o  o 
   f| f| 
    o  o 
   d| d|
    o  o

みたいな木でこの高さは結局N/2になるんだけど、もちろん最初のノードだけN/2回で残りは1回しかマージしない。
じゃあ結局最悪ケースは？というと

         o
         |
      a| - b|
      o      o
      |      | 
    e|-f|  e|-f| 
     o  o   o  o 

完全平衡二分木みたいになるので結局マージ回数は合計NlogN回くらいに抑えられる、という寸法だと思う。
証明とかはしてないけど。
こどふぉのコメント欄にはマージテク（dsu techniqueって言われてたけどこれだいたいマージテクと同じって理解であってるのかな？　あんま自信ない）で最悪logNにできるって書いてあったけどコード読んでもよくわからんかった。
まあなんにせよ後から考えるぶんには面白い問題な気がする。