2021/11/21
ARC129A - Smaller XOR
頑張って桁DPをやっていて、解説を読んで崩れ落ちた…
fn main() { let (r, w) = (std::io::stdin(), std::io::stdout()); let mut sc = IO::new(r.lock(), w.lock()); let n: i64 = sc.read(); let l: i64 = sc.read(); let r: i64 = sc.read(); let ans = solve(n, r) - solve(n, l - 1); println!("{}", ans); } fn solve(n: i64, max: i64) -> i64 { let mut dp = vec![vec![vec![0; 2]; 2]; 2]; dp[0][0][0] = 1; for pos in (0..63).rev() { let max_d = (max >> pos) & 1; let n_d = (n >> pos) & 1; let mut next = vec![vec![vec![0; 2]; 2]; 2]; for started in 0..2 { let is_started = started == 1; for lower in 0..2 { let is_lower = lower == 1; for xor_lower in 0..2 { for next_digit in 0..2 { let next_started = if is_started || next_digit == 1 { 1 } else { 0 }; let next_lower = if is_lower || max_d > next_digit { 1 } else { 0 }; let next_n_lower = if xor_lower == 1 || (next_digit == 1 && n_d == 1) { 1 } else { 0 }; if next_lower != 1 && max_d < next_digit { continue; } if next_n_lower != 1 && next_digit == 1 { continue; } next[next_started][next_lower][next_n_lower] += dp[started][lower][xor_lower]; } } } } dp = next; // eprintln!("{:?}", dp); } let ans = dp[1][0][1] + dp[1][1][1]; ans } pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>); impl<R: std::io::Read, W: std::io::Write> IO<R, W> { pub fn new(r: R, w: W) -> IO<R, W> { IO(r, std::io::BufWriter::new(w)) } pub fn write<S: ToString>(&mut self, s: S) { use std::io::Write; self.1.write_all(s.to_string().as_bytes()).unwrap(); } pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .0 .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn usize0(&mut self) -> usize { self.read::<usize>() - 1 } 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() } }
ARC129D - -1+2-1
面白かった。数列に対する操作を行う時、数列そのものの変化よりも、その数列の階差数列の変化を観察した方が分かりやすくなることがある。この問題はその逆バージョンで、与えられた数列が階差数列だとして、元の数列に対する変化がどのようなものか考えることで解ける。
fn main() { let (r, w) = (std::io::stdin(), std::io::stdout()); let mut sc = IO::new(r.lock(), w.lock()); let n: usize = sc.read(); let a: Vec<i64> = sc.vec(n); if a.iter().sum::<i64>() != 0 { println!("-1"); return; } let mut b = vec![0; n]; for i in 1..n { b[i] = b[i - 1] + a[i - 1]; } assert_eq!(b[0], 0); assert_eq!(b[n - 1] + a[n - 1], 0); let b_sum = b.iter().sum::<i64>(); if b_sum % (n as i64) != 0 { println!("-1"); return; } let one = b_sum / (n as i64); for b in b.iter_mut() { *b -= one; } let mut ans = 0; let mut carry = 0; for i in 0..(3 * n) { if b[i % n] > 0 { carry += b[i % n]; b[i % n] = 0; } else { let t = carry.min(-b[i % n]); carry -= t; b[i % n] += t; } ans += carry; } println!("{}", ans); } pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>); impl<R: std::io::Read, W: std::io::Write> IO<R, W> { pub fn new(r: R, w: W) -> IO<R, W> { IO(r, std::io::BufWriter::new(w)) } pub fn write<S: ToString>(&mut self, s: S) { use std::io::Write; self.1.write_all(s.to_string().as_bytes()).unwrap(); } pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .0 .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn usize0(&mut self) -> usize { self.read::<usize>() - 1 } 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() } }
ARC129C - Multiple of 7
「文字列の[l..r]を切り出して数としてみた時、これがxの倍数となっている」というのは [0..l]00000... と [0..r]000... を割ったあまりが等しいことを意味する。例えば1234567789の77の部分が7の倍数であるのは、1234560000と1234567700のあまりが等しいことと同値。これを見つけられずに謎の解法で殴り倒してしまった。
fn main() { let (r, w) = (std::io::stdin(), std::io::stdout()); let mut sc = IO::new(r.lock(), w.lock()); let n: i64 = sc.read(); let ans = solve(n); for ans in ans { sc.write(ans); } sc.write('\n'); } fn solve(n: i64) -> Vec<i64> { let mut c = vec![]; let mut z = n; while z > 0 { let x = (z as f64 + 100.0).sqrt() as i64 * 2; for k in (1..=x).rev() { if k * (k - 1) / 2 <= z { c.push(k); z -= k * (k - 1) / 2; break; } } } assert!(c.len() <= 7, "n={} c={:?}", n, c); let mut b = vec![]; for (target, count) in c.into_iter().enumerate() { let target = target as i64; let count = if target == 0 { count - 1 } else { count }; for _ in 0..count { b.push(target); } } b.push(0); b.reverse(); let n = b.len(); let mut ans = vec![]; let mut pow10 = 1; for i in (1..n).rev() { let prev = b[i - 1]; let next = b[i]; for x in 1.. { assert!(x < 10); if (prev + x * pow10) % 7 == next { ans.push(x); break; } } pow10 = (pow10 * 10) % 7; } ans.reverse(); ans } pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>); impl<R: std::io::Read, W: std::io::Write> IO<R, W> { pub fn new(r: R, w: W) -> IO<R, W> { IO(r, std::io::BufWriter::new(w)) } pub fn write<S: ToString>(&mut self, s: S) { use std::io::Write; self.1.write_all(s.to_string().as_bytes()).unwrap(); } pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .0 .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn usize0(&mut self) -> usize { self.read::<usize>() - 1 } 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() } }
