AtCoder Beginner Contest 391 E

https://atcoder.jp/contests/abc391/tasks/abc391_e

三分木を作って、再帰的に何回変えればいいか数えます。入力例1なら、010011101を三分割して011だから、1のどちらかを0にすればよいです。最初の1も次の1も1回変えれば0になるので、答えは1です。

// Hierarchical Majority Vote
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn pow(b: usize, e: usize) -> usize {
    if e == 1 {
        b
    }
    else if e % 2 == 1 {
        b * pow(b, e-1)
    }
    else {
        let n = pow(b, e/2);
        n * n
    }
}


//////////////////// Tree ////////////////////

struct Tree {
    a: Vec<i32>
}

impl Tree {
    fn sum_core(&self, i: usize) -> i32 {
        let L = (self.a.len() - 1) / 3;
        if i >= L {
            1
        }
        else {
            let bs: Vec<i32> = (0..3).map(|k| self.a[i*3+k+1]).collect();
            let s = bs.iter().map(|&b| b).sum::<i32>();
            if s == 1 {
                let ns: Vec<i32> = (0..3).filter(|&k| bs[k] == 0).
                                    map(|k| self.sum_core(i*3+k+1)).collect();
                ns.into_iter().min().unwrap()
            }
            else if s == 2 {
                let ns: Vec<i32> = (0..3).filter(|&k| bs[k] == 1).
                                    map(|k| self.sum_core(i*3+k+1)).collect();
                ns.into_iter().min().unwrap()
            }
            else {
                let ns: Vec<i32> = (0..3).map(|k| self.sum_core(i*3+k+1)).
                                                                    collect();
                let max_n: i32 = ns.iter().map(|&n| n).max().unwrap();
                ns.into_iter().sum::<i32>() - max_n
            }
        }
    }
    
    fn sum(&self) -> i32 {
        self.sum_core(0)
    }
    
    fn set_binary(i: usize, a: &mut Vec<i32>, A: &String) {
        let L = (a.len() - 1) / 3;
        if i >= L {
            a[i] = if A.as_bytes()[i-L] == 48 { 0 } else { 1 }
        }
        else {
            let mut s: i32 = 0;
            for k in 0..3 {
                Tree::set_binary(i*3+1+k, a, A);
                s += a[i*3+1+k]
            }
            a[i] = if s < 2 { 0 } else { 1 }
        }
    }
    
    fn create(N: usize, A: String) -> Tree {
        let M = (pow(3, N+1) - 1) / 2;
        let mut a: Vec<i32> = vec![0; M];
        Tree::set_binary(0, &mut a, &A);
        Tree { a }
    }
}


//////////////////// process ////////////////////

fn read_input() -> (usize, String) {
    let N: usize = read();
    let A: String = read();
    (N, A)
}

fn F(N: usize, A: String) -> i32 {
    let tree = Tree::create(N, A);
    tree.sum()
}

fn main() {
    let (N, A) = read_input();
    println!("{}", F(N, A))
}