ABC062/ARC074

Rust でやってみました。標準入出力は他の人のを拝借してきたけど、 println マクロは出力ごとに flush しているようなので注意が必要そう。もっときれいに書けるようになりたい。

A - Grouping

http://abc062.contest.atcoder.jp/tasks/abc062_a

fn next() -> String {
    let mut buffer = String::new();
    std::io::stdin().read_line(&mut buffer).ok();
    return buffer;
}

fn main() {
    let s = next();
    let a: Vec<&str> = s.trim().split(' ').collect();
    let x: i32 = a[0].parse().unwrap();
    let y: i32 = a[1].parse().unwrap();

    let g1 = vec![1, 3, 5, 7, 8, 10, 12];
    let g2 = vec![4, 6, 9, 11];
    let g3 = vec![2];
    if g1.contains(&x) && g1.contains(&y) {
        println!("Yes");
    } else if g2.contains(&x) && g2.contains(&y) {
        println!("Yes");
    } else if g3.contains(&x) && g3.contains(&y) {
        println!("Yes");
    } else {
        println!("No");
    }
}

B - Picture Frame

http://abc062.contest.atcoder.jp/tasks/abc062_b

use std::fmt::Debug;
use std::io;
use std::io::{Read, Stdin};
use std::str;
use std::str::FromStr;

fn main() {
    let mut sc = Scanner::new();
    let h = sc.parse::<usize>();
    let w = sc.parse::<usize>();
    let rows = (0..h).map(|_| sc.parse::<String>()).collect::<Vec<_>>();
    for _ in 0..w + 2 {
        print!("#");
    }
    println!("");
    for row in rows {
        println!("#{}#", row);
    }
    for _ in 0..w + 2 {
        print!("#");
    }
    println!("");
}


struct Scanner {
    stdin: Stdin,
    buf: Vec<u8>,
}

impl Scanner {
    fn new() -> Scanner {
        Scanner {
            stdin: io::stdin(),
            buf: Vec::with_capacity(256),
        }
    }

    fn parse<T: FromStr>(&mut self) -> T
        where <T as FromStr>::Err: Debug
    {
        self.buf.clear();
        let mut it = self.stdin.lock().bytes();
        let mut c = it.next().unwrap().unwrap();
        while c == ' ' as u8 || c == '\n' as u8 {
            c = it.next().unwrap().unwrap();
        }
        while !(c == ' ' as u8 || c == '\n' as u8) {
            self.buf.push(c);
            c = it.next().unwrap().unwrap();
        }
        str::from_utf8(&self.buf).unwrap().parse::<T>().unwrap()
    }
}

C - Chocolate Bar

http://abc062.contest.atcoder.jp/tasks/arc074_a

use std::fmt::Debug;
use std::io;
use std::io::{Read, Stdin};
use std::str;
use std::str::FromStr;
use std::cmp;

fn calc(h: i64, w: i64) -> i64 {
    let mut min: i64 = w;
    for h1 in 1..(h + 1) {
        let s1: i64 = h1 * w;
        let h2: i64 = h - h1;
        let w1: i64 = w / 2;
        let w2: i64 = w - w1;

        let s2: i64 = w1 * h2;
        let s3: i64 = w2 * h2;

        let mut max = cmp::max((s1 - s2).abs(), (s1 - s3).abs());
        max = cmp::max(max, (s2 - s3).abs());

        min = cmp::min(min, max);
    }
    min
}

fn main() {
    let mut sc = Scanner::new();
    let h = sc.parse::<i64>();
    let w = sc.parse::<i64>();
    if h % 3 == 0 || w % 3 == 0 {
        println!("0");
        return;
    }

    let ans = cmp::min(calc(h, w), calc(w, h));
    println!("{}", ans);
}


struct Scanner {
    stdin: Stdin,
    buf: Vec<u8>,
}

impl Scanner {
    fn new() -> Scanner {
        Scanner {
            stdin: io::stdin(),
            buf: Vec::with_capacity(256),
        }
    }

    fn parse<T: FromStr>(&mut self) -> T
        where <T as FromStr>::Err: Debug
    {
        self.buf.clear();
        let mut it = self.stdin.lock().bytes();
        let mut c = it.next().unwrap().unwrap();
        while c == ' ' as u8 || c == '\n' as u8 {
            c = it.next().unwrap().unwrap();
        }
        while !(c == ' ' as u8 || c == '\n' as u8) {
            self.buf.push(c);
            c = it.next().unwrap().unwrap();
        }
        str::from_utf8(&self.buf).unwrap().parse::<T>().unwrap()
    }
}

D - 3N Numbers

http://arc074.contest.atcoder.jp/tasks/arc074_b

use std::fmt::Debug;
use std::io;
use std::io::{Read, Stdin};
use std::str;
use std::str::FromStr;
use std::cmp::Ordering;
use std::collections::BinaryHeap;
use std::usize;
use std::cmp;


fn main() {
    let mut sc = Scanner::new();
    let n = sc.parse::<usize>();
    let mut a: Vec<i64> = vec![0; 3*n];
    for i in 0..(3 * n) {
        a[i] = sc.parse::<i64>();
    }

    let mut heap: BinaryHeap<i64> = BinaryHeap::new();
    let mut sum: i64 = 0;
    let mut prefix_max: Vec<i64> = vec![0;3*n];
    for i in 0..(2 * n) {
        if heap.len() == n {
            let min = -heap.pop().unwrap();
            sum -= min;
            let max = cmp::max(min, a[i]);
            sum += max;
            heap.push(-max);
        } else {
            heap.push(-a[i]);
            sum += a[i];
        }

        if heap.len() == n {
            prefix_max[i] = sum;
        }
    }

    heap.clear();
    sum = 0;
    let mut suffix_min = vec![0;3*n];
    for i in (n..(3 * n)).rev() {
        if heap.len() == n {
            let max = heap.pop().unwrap();
            sum -= max;
            let min = cmp::min(max, a[i]);
            sum += min;
            heap.push(min);
        } else {
            heap.push(a[i]);
            sum += a[i];
        }

        if heap.len() == n {
            suffix_min[i] = sum;
        }
    }

    let mut ans: i64 = -1000000000000000000;
    for i in n..(2 * n + 1) {
        let p = prefix_max[i - 1] as i64;
        let s = suffix_min[i] as i64;
        // println!("{} {}", p, s);
        ans = cmp::max(ans, p - s);
    }
    println!("{}", ans);
}


struct Scanner {
    stdin: Stdin,
    buf: Vec<u8>,
}

impl Scanner {
    fn new() -> Scanner {
        Scanner {
            stdin: io::stdin(),
            buf: Vec::with_capacity(256),
        }
    }

    fn parse<T: FromStr>(&mut self) -> T
        where <T as FromStr>::Err: Debug
    {
        self.buf.clear();
        let mut it = self.stdin.lock().bytes();
        let mut c = it.next().unwrap().unwrap();
        while c == ' ' as u8 || c == '\n' as u8 {
            c = it.next().unwrap().unwrap();
        }
        while !(c == ' ' as u8 || c == '\n' as u8) {
            self.buf.push(c);
            c = it.next().unwrap().unwrap();
        }
        str::from_utf8(&self.buf).unwrap().parse::<T>().unwrap()
    }
}

E - RGB Sequence

http://arc074.contest.atcoder.jp/tasks/arc074_c

use std::fmt::Debug;
use std::io;
use std::io::{Read, Stdin};
use std::str;
use std::str::FromStr;
use std::usize;
use std::cmp;

struct Rule {
    left: usize,
    x: usize,
}

fn main() {
    let mut sc = Scanner::new();
    let n = sc.parse::<usize>();
    let m = sc.parse::<usize>();

    let mut rules: Vec<Vec<Rule>> = Vec::new();
    for _ in 0..(n + 1) {
        rules.push(Vec::new());
    }
    for _ in 0..m {
        let l = sc.parse::<usize>();
        let r = sc.parse::<usize>();
        let x = sc.parse::<usize>();
        rules[r].push(Rule { left: l, x: x });
    }

    let mut dp = vec![vec![vec![0;(n+1)];(n+1)];(n+1)];
    dp[0][0][0] = 1;
    let modulo = 1000000007;
    for r in 0..n {
        for g in 0..n {
            for b in 0..n {
                let k = cmp::max(cmp::max(r, g), b);
                if check(&rules, k + 1, g, b) {
                    dp[k + 1][g][b] += dp[r][g][b];
                    dp[k + 1][g][b] %= modulo;
                }
                if check(&rules, r, k + 1, b) {
                    dp[r][k + 1][b] += dp[r][g][b];
                    dp[r][k + 1][b] %= modulo;
                }
                if check(&rules, r, g, k + 1) {
                    dp[r][g][k + 1] += dp[r][g][b];
                    dp[r][g][k + 1] %= modulo;
                }
            }
        }
    }

    let mut ans = 0;
    for i in 0..n {
        for j in 0..n {
            ans += dp[i][j][n];
            ans %= modulo;
            ans += dp[i][n][j];
            ans %= modulo;
            ans += dp[n][i][j];
            ans %= modulo;
        }
    }
    println!("{}", ans);
}

fn check(rules: &Vec<Vec<Rule>>, r: usize, g: usize, b: usize) -> bool {
    let k = cmp::max(cmp::max(r, g), b);
    for rule in &rules[k] {
        let left = rule.left;
        let mut count = 0;
        if r >= left {
            count += 1;
        }
        if g >= left {
            count += 1;
        }
        if b >= left {
            count += 1;
        }
        if count != rule.x {
            return false;
        }
    }
    return true;
}

struct Scanner {
    stdin: Stdin,
    buf: Vec<u8>,
}

impl Scanner {
    fn new() -> Scanner {
        Scanner {
            stdin: io::stdin(),
            buf: Vec::with_capacity(256),
        }
    }

    fn parse<T: FromStr>(&mut self) -> T
        where <T as FromStr>::Err: Debug
    {
        self.buf.clear();
        let mut it = self.stdin.lock().bytes();
        let mut c = it.next().unwrap().unwrap();
        while c == ' ' as u8 || c == '\n' as u8 {
            c = it.next().unwrap().unwrap();
        }
        while !(c == ' ' as u8 || c == '\n' as u8) {
            self.buf.push(c);
            c = it.next().unwrap().unwrap();
        }
        str::from_utf8(&self.buf).unwrap().parse::<T>().unwrap()
    }
}

F - Lotus Leaves

http://arc074.contest.atcoder.jp/tasks/arc074_d

use std::fmt::Debug;
use std::io;
use std::io::{Read, Stdin};
use std::str;
use std::str::FromStr;
use std::usize;
use std::cmp;
use std::collections::vec_deque::VecDeque;
use std::i64::MAX;

pub struct Edge {
    pub to: usize,
    pub rev: usize,
    pub cap: i64,
}

struct Dinitz {
    g: Vec<Vec<Edge>>,
    level: Vec<i32>,
    iter: Vec<usize>,
}

impl Dinitz {
    fn new(v: usize) -> Dinitz {
        let mut g: Vec<Vec<Edge>> = Vec::new();
        for _ in 0..v {
            g.push(Vec::new());
        }
        Dinitz {
            g: g,
            level: vec![0;v],
            iter: vec![0;v],
        }
    }

    fn add_edge(&mut self, from: usize, to: usize, cap: i64) {
        let to_len = self.g[to].len();
        let from_len = self.g[from].len();
        self.g[from].push(Edge {
                              to: to,
                              rev: to_len,
                              cap: cap,
                          });
        self.g[to].push(Edge {
                            to: from,
                            rev: from_len,
                            cap: 0,
                        });
    }

    fn dfs(&mut self, v: usize, t: usize, f: i64) -> i64 {
        if v == t {
            return f;
        }
        while self.iter[v] < self.g[v].len() {

            let (e_cap, e_to, e_rev);
            {
                let ref e = self.g[v][self.iter[v]];
                e_cap = e.cap;
                e_to = e.to;
                e_rev = e.rev;
            }
            if e_cap > 0 && self.level[v] < self.level[e_to] {
                let d = self.dfs(e_to, t, cmp::min(f, e_cap));
                if d > 0 {
                    {
                        let ref mut e = self.g[v][self.iter[v]];
                        e.cap -= d;
                    }
                    {
                        let ref mut rev_edge = self.g[e_to][e_rev];
                        rev_edge.cap += d;
                    }
                    return d;
                }
            }
            self.iter[v] += 1;
        }

        return 0;
    }

    fn bfs(&mut self, s: usize) {
        let v = self.level.len();
        self.level = vec![-1;v];
        self.level[s] = 0;
        let mut deque = VecDeque::new();
        deque.push_back(s);
        while !deque.is_empty() {
            let v = deque.pop_front().unwrap();
            for e in &self.g[v] {
                if e.cap > 0 && self.level[e.to] < 0 {
                    self.level[e.to] = self.level[v] + 1;
                    deque.push_back(e.to);
                }
            }
        }
    }

    fn max_flow(&mut self, s: usize, t: usize) -> i64 {
        let v = self.level.len();
        let mut flow: i64 = 0;
        loop {
            self.bfs(s);
            if self.level[t] < 0 {
                return flow;
            }
            self.iter = vec![0;v];
            loop {
                let f = self.dfs(s, t, MAX);
                if f == 0 {
                    break;
                }
                flow += f;
            }
        }
    }
}

fn main() {
    let mut sc = Scanner::new();
    let h = sc.parse::<usize>();
    let w = sc.parse::<usize>();
    let n = h + w + 2;
    let source = h + w;
    let sink = source + 1;

    let mut dinitz = Dinitz::new(n);

    let mut si = 0;
    let mut sj = 0;
    let mut ti = 0;
    let mut tj = 0;
    let rows = (0..h).map(|_| sc.parse::<String>()).collect::<Vec<_>>();
    for i in 0..h {
        let row = rows[i].as_bytes();
        for j in 0..w {
            match row[j] {
                b'S' => {
                    si = i;
                    sj = j;
                    dinitz.add_edge(source, i, MAX);
                    dinitz.add_edge(source, h + j, MAX);
                }
                b'T' => {
                    ti = i;
                    tj = j;
                    dinitz.add_edge(i, sink, MAX);
                    dinitz.add_edge(h + j, sink, MAX);
                }
                b'o' => {
                    dinitz.add_edge(i, h + j, 1);
                    dinitz.add_edge(h + j, i, 1);
                }
                _ => {}
            }
        }
    }

    if si == ti || sj == tj {
        println!("-1");
        return;
    }

    let f = dinitz.max_flow(source, sink);
    println!("{}", f);
}

struct Scanner {
    stdin: Stdin,
    buf: Vec<u8>,
}

impl Scanner {
    fn new() -> Scanner {
        Scanner {
            stdin: io::stdin(),
            buf: Vec::with_capacity(256),
        }
    }

    fn parse<T: FromStr>(&mut self) -> T
        where <T as FromStr>::Err: Debug
    {
        self.buf.clear();
        let mut it = self.stdin.lock().bytes();
        let mut c = it.next().unwrap().unwrap();
        while c == ' ' as u8 || c == '\n' as u8 {
            c = it.next().unwrap().unwrap();
        }
        while !(c == ' ' as u8 || c == '\n' as u8) {
            self.buf.push(c);
            c = it.next().unwrap().unwrap();
        }
        str::from_utf8(&self.buf).unwrap().parse::<T>().unwrap()
    }
}