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() } }