結果

問題 No.2069 み世界数式
ユーザー akakimidori
提出日時 2022-09-01 21:11:26
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 24 ms / 2,000 ms
コード長 3,969 bytes
コンパイル時間 11,744 ms
コンパイル使用メモリ 402,024 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-24 16:08:46
合計ジャッジ時間 13,580 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

fn main() {
    let (m, ans, mut expr) = read();
    let res = Solver::solve(m, &expr);
    if res.0[ans].0 {
        let mut x = 0;
        for s in expr.iter_mut() {
            if *s == b'$' || *s == b'&' {
                *s = res.0[ans].1[x];
                x += 1;
            }
        }
        let ans = expr.iter().map(|c| *c as char).collect::<String>();
        println!("{}", ans);
    } else {
        println!("-1");
    }
}

fn read() -> (usize, usize, Vec<u8>) {
    let mut s = String::new();
    use std::io::*;
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let m = it.next().unwrap().parse().unwrap();
    let ans = it.next().unwrap().parse().unwrap();
    let expr = it.next().unwrap().bytes().collect();
    (m, ans, expr)
}

struct Solver<'a> {
    m: usize,
    s: &'a [u8],
    pos: usize,
}

impl<'a> Solver<'a> {
    fn solve(m: usize, s: &'a [u8]) -> DP {
        let mut state = Solver { m: m, s: s, pos: 0 };
        let res = state.expression();
        assert!(state.pos == state.s.len());
        res
    }
    fn next(&self) -> Option<u8> {
        self.s.get(self.pos).cloned()
    }
    fn eat(&mut self) -> Option<u8> {
        self.s.get(self.pos).cloned().map(|c| {
            self.pos += 1;
            c
        })
    }
    fn expression(&mut self) -> DP {
        let mut res = self.term();
        while self.next().map_or(false, |c| c == b'$') {
            self.eat();
            let rhs = self.term();
            res = res.add_sub(&rhs);
        }
        res
    }
    fn term(&mut self) -> DP {
        let mut res = self.factor();
        while self.next().map_or(false, |c| c == b'&') {
            self.eat();
            let rhs = self.factor();
            res = res.mul_div(&rhs);
        }
        res
    }
    fn factor(&mut self) -> DP {
        let c = self.next().unwrap();
        if c == b'(' {
            self.eat();
            let res = self.expression();
            assert_eq!(self.eat(), Some(b')'));
            res
        } else {
            assert!(b'0' <= c && c <= b'9');
            let mut v = 0;
            while self.next().map_or(false, |c| b'0' <= c && c <= b'9') {
                v = 10 * v + (self.eat().unwrap() - b'0') as usize;
                assert!(v <= self.m);
            }
            DP::new(self.m, v)
        }
    }
}

struct DP(Vec<(bool, Vec<u8>)>);

impl DP {
    fn zero(m: usize) -> Self {
        DP(vec![(false, vec![]); m + 1])
    }
    fn new(m: usize, x: usize) -> Self {
        assert!(1 <= m && m <= 300);
        assert!(x <= m);
        let mut dp = vec![(false, vec![]); m + 1];
        dp[x].0 = true;
        DP(dp)
    }
    fn add_sub(&self, rhs: &Self) -> Self {
        assert!(self.0.len() == rhs.0.len());
        let mut res = DP::zero(self.0.len() - 1);
        for (l, a) in self.0.iter().enumerate().filter(|p| p.1 .0) {
            for (r, b) in rhs.0.iter().enumerate().filter(|p| p.1 .0) {
                res.fill(l + r, a, b'+', b);
                res.fill(l - r, a, b'-', b);
            }
        }
        res
    }
    fn mul_div(&self, rhs: &Self) -> Self {
        assert!(self.0.len() == rhs.0.len());
        let mut res = DP::zero(self.0.len() - 1);
        for (l, a) in self.0.iter().enumerate().filter(|p| p.1 .0) {
            for (r, b) in rhs.0.iter().enumerate().filter(|p| p.1 .0) {
                res.fill(l * r, a, b'*', b);
                if r > 0 {
                    res.fill(l / r, a, b'/', b);
                }
            }
        }
        res
    }
    fn fill(&mut self, x: usize, a: &(bool, Vec<u8>), c: u8, b: &(bool, Vec<u8>)) {
        if x < self.0.len() && !self.0[x].0 {
            self.0[x].0 = true;
            self.0[x].1 =
                a.1.iter()
                    .cloned()
                    .chain(std::iter::once(c))
                    .chain(b.1.iter().cloned())
                    .collect();
        }
    }
}
0