AtCoder Beginner Contest 132 D - Blue and Red Balls
問題
解法
K個の青いボールをi個の区間に分け、かつ、全ての区間が1個以上ボールを含むような青いボールの分け方は である。同様に考えて赤いボールの分け方を求め、この2つの積が答えになる。
const MOD: usize = 1e9 as usize + 7; fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let n: usize = sc.read(); let blue_ball: usize = sc.read(); let c = Combination::new(n * 2 + 1, MOD); let red_ball = n - blue_ball; for seg in 1..(blue_ball + 1) { if seg > blue_ball || seg - 1 > red_ball { println!("0"); continue; } let free_blue = blue_ball - seg; let free_red = red_ball - (seg - 1); let ans = c.get(free_blue + seg - 1, free_blue) * c.get(free_red + seg + 1 - 1, free_red); println!("{}", ans % MOD); } } pub struct Combination { fact: Vec<usize>, inv_fact: Vec<usize>, modulo: usize, } impl Combination { pub fn new(max: usize, modulo: usize) -> Combination { let mut inv = vec![0; max + 1]; let mut fact = vec![0; max + 1]; let mut inv_fact = vec![0; max + 1]; inv[1] = 1; for i in 2..(max + 1) { inv[i] = inv[modulo % i] * (modulo - modulo / i) % modulo; } fact[0] = 1; inv_fact[0] = 1; for i in 0..max { fact[i + 1] = fact[i] * (i + 1) % modulo; } for i in 0..max { inv_fact[i + 1] = inv_fact[i] * inv[i + 1] % modulo; } Combination { fact: fact, inv_fact: inv_fact, modulo: modulo, } } pub fn get(&self, x: usize, y: usize) -> usize { assert!(x >= y); self.fact[x] * self.inv_fact[y] % self.modulo * self.inv_fact[x - y] % self.modulo } pub fn h(&self, n: usize, r: usize) -> usize { self.get(n + r - 1, r) } } pub struct Scanner<R> { stdin: R, } impl<R: std::io::Read> Scanner<R> { pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .stdin .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n') .take_while(|&b| b != b' ' && b != b'\n') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }
今日解いた問題
バグらせずに実装するのが地味に大変な問題だと思う。
use std::cmp; use std::collections::BTreeMap; fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let h: usize = sc.read(); let w: usize = sc.read(); let mut board = vec![vec![false; w]; h]; for i in 0..h { let s = sc.chars(); for j in 0..w { board[i][j] = s[j] == '#'; } } let mut inv_board = vec![vec![false; w]; h]; for i in 0..h { for j in 0..w { inv_board[i][j] = board[h - 1 - i][j]; } } let ans1 = solve(&board); let ans2 = solve(&inv_board); let mut ans = ans1 + ans2; let mut map = BTreeMap::new(); for x in 0..h { for y in 0..w { if board[x][y] { // y = -x + l let l = x + y; map.entry(l).or_insert(Vec::new()).push((x, y)); } } } for v in map.values() { for j in 0..v.len() { for i in 0..j { let (x1, y1) = v[i]; let (x2, y2) = v[j]; let d = y1 - y2; let mut c = vec![]; if x1 >= d { c.push((x1 - d, y2)); } if y2 >= d { c.push((x1, y2 - d)); } if y1 + d < w { c.push((x2, y1 + d)); } if x2 + d < h { c.push((x2 + d, y1)); } for (x3, y3) in c.into_iter() { if board[x3][y3] { ans -= 1; } } } } } println!("{}", ans); } fn solve(board: &Vec<Vec<bool>>) -> usize { let h = board.len(); let w = board[0].len(); let mut map = BTreeMap::new(); for x in 0..h { for y in 0..w { if board[x][y] { // y = -x + l let l = x + y; map.entry(l).or_insert(Vec::new()).push((x, y)); } } } let sum: BTreeMap<usize, Vec<usize>> = map .iter() .map(|(&l, v)| { let mut board = vec![0; h]; for &(x, _) in v.iter() { board[x] = 1; } let mut sum = vec![0; h + 1]; for i in 0..h { sum[i + 1] = sum[i] + board[i]; } (l, sum) }) .collect(); let mut ans = 0; for (&l, v) in map.iter() { for j in 0..v.len() { for i in 0..j { let (x1, y1) = v[i]; let (x2, y2) = v[j]; assert_eq!(x2 - x1, y1 - y2); let d = x2 - x1; if l >= 2 * d { let lower = if x1 >= d { x1 - d } else { 0 }; let upper = x1 + 1; let l3 = l - 2 * d; if let Some(sum) = sum.get(&l3) { ans += sum[upper] - sum[lower]; } } let lower = x2; let upper = cmp::min(x2 + d + 1, h); let l3 = l + 2 * d; if let Some(sum) = sum.get(&l3) { ans += sum[upper] - sum[lower]; } } } } ans } pub struct Scanner<R> { stdin: R, } impl<R: std::io::Read> Scanner<R> { pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .stdin .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n') .take_while(|&b| b != b' ' && b != b'\n') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }
use std::cmp; fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let n: usize = sc.read(); let mut edges = vec![]; let mut left = 0; let mut right = 0; for i in 0..n { let a: u64 = sc.read(); let b: u64 = sc.read(); left += a; right += b; edges.push((a, i, true)); edges.push((b, i, false)); } edges.sort(); let mut ans = cmp::min(left, right); let mut count = vec![0; n]; let mut sum = 0; for i in 0..n { let (cost, i, _) = edges[i]; count[i] += 1; sum += cost; } if count.iter().any(|&x| x != 1) { println!("{}", cmp::min(ans, sum)); return; } if edges[n - 1].1 != edges[n].1 { sum -= edges[n - 1].0; sum += edges[n].0; println!("{}", cmp::min(ans, sum)); return; } ans = cmp::min(ans, sum - edges[n - 2].0 + edges[n].0); ans = cmp::min(ans, sum - edges[n - 1].0 + edges[n + 1].0); println!("{}", ans); } pub struct Scanner<R> { stdin: R, } impl<R: std::io::Read> Scanner<R> { pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .stdin .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n') .take_while(|&b| b != b' ' && b != b'\n') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }
VSCode で Rust で競技プログラミングをするときの設定
拡張機能と RLS を入れる
task の登録
{ // See https://go.microsoft.com/fwlink/?LinkId=733558 // for the documentation about the tasks.json format "version": "2.0.0", "tasks": [ { "label": "cargo run", "type": "shell", "command": "RUST_BACKTRACE=1", "args": [ "cargo", "run", "--bin", "${fileBasenameNoExtension}" ], "group": { "kind": "build", "isDefault": true } } ] }
スニペットの登録
{ // Place your snippets for rust here. Each snippet is defined under a snippet name and has a prefix, body and // description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are: // $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the // same ids are connected. // Example: // "Print to console": { // "prefix": "log", // "body": [ // "console.log('$1');", // "$2" // ], // "description": "Log output to console" // } "Scanner and main": { "prefix": "scanner", "body": [ "fn main() {", " let s = std::io::stdin();", " let mut sc = Scanner { stdin: s.lock() };", " $1", "}", "", "pub struct Scanner<R> {", " stdin: R,", "}", "", "impl<R: std::io::Read> Scanner<R> {", " pub fn read<T: std::str::FromStr>(&mut self) -> T {", " use std::io::Read;", " let buf = self", " .stdin", " .by_ref()", " .bytes()", " .map(|b| b.unwrap())", " .skip_while(|&b| b == b' ' || b == b'\\n' || b == b'\\r')", " .take_while(|&b| b != b' ' && b != b'\\n' && b != b'\\r')", " .collect::<Vec<_>>();", " unsafe { std::str::from_utf8_unchecked(&buf) }", " .parse()", " .ok()", " .expect(\"Parse error.\")", " }", " pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {", " (0..n).map(|_| self.read()).collect()", " }", " pub fn chars(&mut self) -> Vec<char> {", " self.read::<String>().chars().collect()", " }", "}" ] } }
今日解いた問題
コード
fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let n: usize = sc.read(); let l: usize = sc.read(); let t: usize = sc.read(); let xw: Vec<(usize, usize)> = (0..n).map(|_| (sc.read(), sc.read())).collect(); let mut clockwise = 0; let mut counter_clock_wise = 0; for (x, w) in xw.iter().cloned() { if w == 1 { clockwise += (x + t) / l; } else if t > x { counter_clock_wise += ((l - x) + t - 1) / l; } } let mut next = xw .into_iter() .map(|(x, w)| { if w == 1 { (x + t) % l } else { (l - ((l - x) + t) % l) % l } }) .collect::<Vec<_>>(); next.sort(); let over = clockwise % n + n - counter_clock_wise % n; for i in 0..n { println!("{}", next[(i + over) % n]); } } pub struct Scanner<R> { stdin: R, } impl<R: std::io::Read> Scanner<R> { pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .stdin .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }
コード
use std::cmp; use std::collections::VecDeque; const INF: i32 = 1e9 as i32; const DIR: [(i32, i32); 4] = [(0, -1), (0, 1), (-1, 0), (1, 0)]; fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let h: usize = sc.read(); let w: usize = sc.read(); let k: i32 = sc.read(); let board: Vec<_> = (0..h).map(|_| sc.chars()).collect(); let mut dist = vec![vec![INF; w]; h]; let mut si = 0; let mut sj = 0; for i in 0..h { for j in 0..w { if board[i][j] == 'S' { dist[i][j] = 0; si = i; sj = j; } } } let mut q = VecDeque::new(); q.push_back((0, 0, si, sj)); for _ in 0.. { let mut next_q = VecDeque::new(); while let Some((time, open, i, j)) = q.pop_front() { if i == h - 1 || j == w - 1 || i == 0 || j == 0 { let turn = (time + k - 1) / k; println!("{}", turn); return; } for (di, dj) in DIR.iter().cloned() { let ni = (i as i32) + di; let nj = (j as i32) + dj; if ni < 0 || nj < 0 { continue; } let ni = ni as usize; let nj = nj as usize; if ni >= h || nj >= w { continue; } if board[ni][nj] == '#' && open > 0 && dist[ni][nj] > time + 1 { dist[ni][nj] = time + 1; if (time + 1) % k == 0 { next_q.push_back((time + 1, k, ni, nj)); } else { q.push_back((time + 1, open - 1, ni, nj)); } } else if board[ni][nj] == '.' && dist[ni][nj] > time + 1 { dist[ni][nj] = time + 1; if (time + 1) % k == 0 { next_q.push_back((time + 1, k, ni, nj)); } else { q.push_back((time + 1, open, ni, nj)); } } } let next_time = (time + k) / k * k; next_q.push_front((next_time, k, i, j)); } q = next_q; } } pub struct Scanner<R> { stdin: R, } impl<R: std::io::Read> Scanner<R> { pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .stdin .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }
問題
解説動画のとおりにやった。
1 ... a-1, a+1, ... , x
1 ... b-1, b+1, ... , x
という2つのほぼ等差数列から作れる積の最大値が ab を超えないような x を二分探索する。
コード
use std::cmp; fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let q: usize = sc.read(); for _ in 0..q { let a: usize = sc.read(); let b: usize = sc.read(); let (a, b) = if a > b { (b, a) } else { (a, b) }; let mut ok = a - 1; let mut ng = 1e10 as usize; while ng - ok > 1 { let x = (ok + ng) / 2; let mut max = 0; if x >= b - 1 { // 1 ... a-1 a+1 ... x-b+1 x-b+2 ... x // x ... x-a+2 x-a+1 ... b+1 b-1 ... 1 max = get_max(1, a - 1, x, x + 2 - a); max = cmp::max(max, get_max(a + 1, x - (b - 1), x - (a - 1), b + 1)); max = cmp::max(max, get_max(x + 2 - b, x, b - 1, 1)); } else { // 1 ... a-1 a+1 ... x // x-1 ... x-a+1 x-a ... 1 max = get_max(1, a - 1, x - 1, x - (a - 1)); max = cmp::max(max, get_max(a + 1, x, x - a, 1)); } if max < a * b { ok = x; } else { ng = x; } } println!("{}", if a <= ok { ok - 1 } else { ok }); } } fn get_max(from_a: usize, to_a: usize, from_b: usize, to_b: usize) -> usize { if from_a > to_a { return 0; } assert_eq!(to_a + 1 - from_a, from_b + 1 - to_b); let mut m = (from_a + from_b) / 2; let mut max = cmp::max(from_a * from_b, to_a * to_b); if from_a <= m && m <= to_a { let da = m - from_a; let b = from_b - da; max = cmp::max(max, m * b); } m += 1; if from_a <= m && m <= to_a { let da = m - from_a; let b = from_b - da; max = cmp::max(max, m * b); } max } pub struct Scanner<R> { stdin: R, } impl<R: std::io::Read> Scanner<R> { pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .stdin .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }
コード
fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let h: usize = sc.read(); let w: usize = sc.read(); let board: Vec<Vec<char>> = (0..h).map(|_| sc.chars()).collect(); let mut blue = vec![vec!['.'; w]; h]; let mut red = vec![vec!['.'; w]; h]; for i in 0..h { for j in 0..w { if j == 0 { red[i][j] = '#'; } else if j == w - 1 { blue[i][j] = '#'; } else if i % 2 == 0 { red[i][j] = '#'; } else { blue[i][j] = '#'; } if board[i][j] == '#' { red[i][j] = '#'; blue[i][j] = '#'; } } } for i in 0..h { for j in 0..w { print!("{}", red[i][j]); } println!(); } println!(); for i in 0..h { for j in 0..w { print!("{}", blue[i][j]); } println!(); } } pub struct Scanner<R> { stdin: R, } impl<R: std::io::Read> Scanner<R> { pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .stdin .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }
コード
use std::collections::VecDeque; fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let n = sc.read(); let m: usize = sc.read(); let mut graph = vec![vec![]; n]; for _ in 0..m { let a = sc.read::<usize>() - 1; let b = sc.read::<usize>() - 1; graph[a].push(b); graph[b].push(a); } let q: usize = sc.read(); let mut potential = vec![-1; n]; let mut color = vec![0; n]; let vdc: Vec<_> = (0..q) .map(|_| (sc.read::<usize>() - 1, sc.read::<i64>(), sc.read::<usize>())) .collect(); for (root, distance, c) in vdc.into_iter().rev() { if potential[root] >= distance { continue; } let mut q = VecDeque::new(); q.push_back(root); if color[root] == 0 { color[root] = c; } potential[root] = distance; while let Some(v) = q.pop_front() { if potential[v] == 0 { continue; } for &next in graph[v].iter() { if color[next] == 0 { color[next] = c; } if potential[next] < potential[v] - 1 { potential[next] = potential[v] - 1; q.push_back(next); } } } } for c in color.into_iter() { println!("{}", c); } } pub struct Scanner<R> { stdin: R, } impl<R: std::io::Read> Scanner<R> { pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .stdin .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }
Google Code Jam 2019 Round 1B - Fair Fight
解法
となるような (l, r) の組の数を求めて全体から引くことにする。
と
は c と d を入れ替えることで独立に同じように求めることができる。
各 i について c_i が最大となるような c の区間を求める。これは Sparse Table で二分探索を二回やると求まる。次に、この区間内で となるような l と
となるような r を求める。
コード
use self::sparse_table::SparseTable; use std::cmp; fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let t: usize = sc.read(); for t in 0..t { let n: usize = sc.read(); let k: i64 = sc.read(); let c: Vec<i64> = sc.vec(n); let d: Vec<i64> = sc.vec(n); let ans = n * (n + 1) / 2 - solve(&c, &d, k) - solve(&d, &c, k); println!("Case #{}: {}", t + 1, ans); } } fn solve(c: &[i64], d: &[i64], k: i64) -> usize { let n = c.len(); let c_st = SparseTable::from(c, 0, cmp::max); let d_st = SparseTable::from(d, 0, cmp::max); (0..n) .filter(|&i| d[i] < c[i] - k) .map(|i| { let mut ng = n + 1; let mut ok = i + 1; while ng - ok > 1 { let m = (ok + ng) >> 1; if c_st.get(i, m) <= c[i] { ok = m; } else { ng = m; } } let right = ok; let mut ok = i as i64; let mut ng = -1; while ok - ng > 1 { let m = (ok + ng) >> 1; if c_st.get(m as usize, i) < c[i] { ok = m; } else { ng = m; } } let left = ok; let mut ok = i + 1; let mut ng = right + 1; while ng - ok > 1 { let m = (ok + ng) >> 1; if d_st.get(i, m) < c[i] - k { ok = m; } else { ng = m; } } let right = ok; let mut ok = i as i64; let mut ng = left - 1; while ok - ng > 1 { let m = (ok + ng) >> 1; if d_st.get(m as usize, i + 1) < c[i] - k { ok = m; } else { ng = m; } } let left = ok as usize; (i - left + 1) * (right - i) }) .sum() } pub mod sparse_table { use std::cmp; pub struct SparseTable<T, F> { data: Vec<Vec<T>>, op: F, } impl<T, F> SparseTable<T, F> where T: Copy, F: Fn(T, T) -> T, { pub fn from(v: &[T], init: T, op: F) -> Self { let size = v.len().next_power_of_two(); let count = size.trailing_zeros() as usize + 1; let mut data = vec![vec![init; size]; count]; for (i, v) in v.iter().cloned().enumerate() { data[0][i] = v; } for c in 1..count { for i in 0..size { let next = cmp::min(size - 1, i + (1 << (c - 1))); data[c][i] = op(data[c - 1][i], data[c - 1][next]); } } Self { data: data, op: op } } /// get the result for [l, r) pub fn get(&self, l: usize, r: usize) -> T { assert!(l < r, "l={} r={}", l, r); let length = r - l; if length == 1 { return self.data[0][l]; } let block_size = length.next_power_of_two() >> 1; let c = block_size.trailing_zeros() as usize; let left = self.data[c][l]; let right = self.data[c][r - block_size]; (self.op)(left, right) } } } pub struct Scanner<R> { stdin: R, } impl<R: std::io::Read> Scanner<R> { pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .stdin .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }
Google Code Jam 2019 Round 1B - Draupnir
解法
は入力を 64bit 整数に収めるためのものではなく、解法の重要なポイントになる。D=200 で得られる入力は
である。
であることから
を求めることができる。これらを利用して D=50 の入力から
を求めることができる。
コード
fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let t: usize = sc.read(); let _: usize = sc.read(); for _ in 0..t { println!("200"); let day200: u64 = sc.read(); let ring4 = day200 / (1 << 50); let ring5 = (day200 - ring4 * (1 << 50)) / (1 << 40); let ring6 = (day200 - ring4 * (1 << 50) - ring5 * (1 << 40)) / (1 << 33); println!("50"); let day50: u64 = sc.read(); let day50 = day50 - ring4 * (1 << 12) - ring5 * (1 << 10) - ring6 * (1 << 8); let ring1 = day50 / (1 << 50); let ring2 = (day50 - ring1 * (1 << 50)) / (1 << 25); let ring3 = (day50 - ring1 * (1 << 50) - ring2 * (1 << 25)) / (1 << 16); println!( "{} {} {} {} {} {}", ring1, ring2, ring3, ring4, ring5, ring6 ); let response: i64 = sc.read(); assert_eq!(response, 1); } } pub struct Scanner<R> { stdin: R, } impl<R: std::io::Read> Scanner<R> { pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .stdin .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }
