AtCoder Regular Contest 109 参加記
C - Large RPS Tournament
[l, r) の結果を全ての l, r について求めたいが、これは実は状態数がかなり少ないので、愚直なメモ化再帰を書くだけで通る。
use std::collections::BTreeMap; 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 k: usize = sc.read(); let s = sc.chars(); let (win, _) = dp(0, k, &s, &mut BTreeMap::new()); println!("{}", win); } fn dp( offset: usize, k: usize, s: &[char], memo: &mut BTreeMap<(usize, usize), (char, usize)>, ) -> (char, usize) { if let Some(&(win, offset)) = memo.get(&(offset, k)) { return (win, offset); } if k == 1 { let left = s[offset]; let right = s[(offset + 1) % s.len()]; let next_offset = (offset + 2) % s.len(); let win = pick_win(left, right); return (win, next_offset); } let (left, next_offset) = dp(offset, k - 1, s, memo); let (right, next_offset) = dp(next_offset, k - 1, s, memo); let win = pick_win(left, right); memo.insert((offset, k), (win, next_offset)); (win, next_offset) } fn pick_win(left: char, right: char) -> char { if left == right { left } else { match (left, right) { ('R', 'S') | ('S', 'R') => 'R', ('S', 'P') | ('P', 'S') => 'S', ('P', 'R') | ('R', 'P') => 'P', _ => unreachable!(), } } } 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) -> Self { Self(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 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() } }
結果
- 赤パフォ: ABCE 72:29
- 橙パフォ: ABCD 96:51
- 黄パフォ: ABC 36:15
- 自分: ABC 62:03
感想
結果的には(自分の実力帯では)ABCの3問早解き勝負だったのだが、そこで勝てなかった。
早解きをするか、あと1問を頑張るしかないが…