結果

問題 No.2926 Botaoshi
ユーザー ぱるまぱるま
提出日時 2024-10-12 16:43:16
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 21 ms / 2,000 ms
コード長 5,610 bytes
コンパイル時間 14,927 ms
コンパイル使用メモリ 379,792 KB
実行使用メモリ 13,824 KB
最終ジャッジ日時 2024-10-12 16:43:34
合計ジャッジ時間 16,859 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 1 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 1 ms
5,248 KB
testcase_06 AC 1 ms
5,248 KB
testcase_07 AC 1 ms
5,248 KB
testcase_08 AC 1 ms
5,248 KB
testcase_09 AC 1 ms
5,248 KB
testcase_10 AC 1 ms
5,248 KB
testcase_11 AC 1 ms
5,248 KB
testcase_12 AC 19 ms
13,796 KB
testcase_13 AC 19 ms
13,412 KB
testcase_14 AC 20 ms
13,532 KB
testcase_15 AC 1 ms
5,248 KB
testcase_16 AC 15 ms
9,984 KB
testcase_17 AC 18 ms
12,032 KB
testcase_18 AC 4 ms
5,248 KB
testcase_19 AC 13 ms
8,576 KB
testcase_20 AC 6 ms
5,248 KB
testcase_21 AC 10 ms
7,168 KB
testcase_22 AC 11 ms
8,320 KB
testcase_23 AC 3 ms
5,248 KB
testcase_24 AC 13 ms
9,344 KB
testcase_25 AC 4 ms
5,248 KB
testcase_26 AC 15 ms
11,108 KB
testcase_27 AC 10 ms
7,424 KB
testcase_28 AC 3 ms
5,248 KB
testcase_29 AC 2 ms
5,248 KB
testcase_30 AC 6 ms
5,248 KB
testcase_31 AC 5 ms
5,248 KB
testcase_32 AC 8 ms
5,760 KB
testcase_33 AC 15 ms
10,128 KB
testcase_34 AC 14 ms
8,960 KB
testcase_35 AC 1 ms
5,248 KB
testcase_36 AC 20 ms
13,808 KB
testcase_37 AC 20 ms
13,796 KB
testcase_38 AC 20 ms
13,792 KB
testcase_39 AC 20 ms
13,824 KB
testcase_40 AC 20 ms
13,748 KB
testcase_41 AC 20 ms
13,824 KB
testcase_42 AC 19 ms
13,724 KB
testcase_43 AC 21 ms
13,824 KB
testcase_44 AC 19 ms
13,312 KB
testcase_45 AC 19 ms
13,260 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//#[derive_readable]
#[derive(Debug, Clone)]
struct Problem {
    n: usize,
    ss: Vec<char>,
}

impl Problem {
    fn read() -> Problem {
        input! {
            n: usize,
            ss: Chars,
        }
        Problem { n, ss }
    }

    fn solve(&self) -> Answer {
        let n = self.n;
        let ss = &self.ss;
        // もしかしてACLない？
        let m = 998244353;
        let mut dp = vec![vec![0; 3]; n];
        let left = 0;
        let up = 1;
        let right = 2;
        // 1文字見ておく
        match ss[0] {
            'L' => {
                dp[0][left] = 1;
            }
            'U' => {
                dp[0][up] = 1;
            }
            'R' => {
                dp[0][right] = 1;
            }
            _ => {
                dp[0][left] = 1;
                dp[0][up] = 1;
                dp[0][right] = 1;
            }
        }

        for i in 1..n {
            if ss[i] == 'L' || ss[i] == '.' {
                dp[i][left] = (dp[i - 1][left] + dp[i - 1][up]) % m;
            }
            if ss[i] == 'U' || ss[i] == '.' {
                dp[i][up] = (dp[i - 1][left] + dp[i - 1][up] + dp[i - 1][right]) % m;
            }
            if ss[i] == 'R' || ss[i] == '.' {
                dp[i][right] = (dp[i - 1][left] + dp[i - 1][up] + dp[i - 1][right]) % m;
            }
        }

        //dbg!(&dp);

        let ans = (dp[n - 1][left] + dp[n - 1][up] + dp[n - 1][right]) % m;
        Answer { ans }
    }

    #[allow(dead_code)]
    fn solve_naive(&self) -> Answer {
        todo!();
        // let ans = 0;
        // Answer { ans }
    }
}

#[derive(Clone, Debug, PartialEq, Eq)]
struct Answer {
    ans: i64,
}

impl Answer {
    fn print(&self) {
        println!("{}", self.ans);
    }
}

fn main() {
    Problem::read().solve().print();
}

#[cfg(test)]
mod tests {
    #[allow(unused_imports)]
    use super::*;
    #[allow(unused_imports)]
    use rand::{rngs::SmallRng, seq::SliceRandom, *};

    #[test]
    fn test_problem() {
        assert_eq!(1 + 1, 2);
    }

    #[allow(dead_code)]
    #[derive(Debug)]
    struct WrongTestCase {
        problem: Problem,
        main_ans: Answer,
        naive_ans: Answer,
    }

    #[allow(dead_code)]
    fn check(p: &Problem) -> Option<WrongTestCase> {
        let main_ans = p.solve();
        let naive_ans = p.solve_naive();
        if main_ans != naive_ans {
            Some(WrongTestCase {
                problem: p.clone(),
                main_ans,
                naive_ans,
            })
        } else {
            None
        }
    }

    #[allow(dead_code)]
    fn make_random_problem(rng: &mut SmallRng) -> Problem {
        todo!()
        // let n = rng.gen_range(1..=10);
        // let p = Problem { _a: n };
        // println!("{:?}", &p);
        // p
    }

    #[allow(unreachable_code)]
    #[test]
    fn test_with_naive() {
        let num_tests = 0;
        let max_wrong_case = 10; // この件数間違いが見つかったら打ち切り
        let mut rng = SmallRng::seed_from_u64(42);
        // let mut rng = SmallRng::from_entropy();
        let mut wrong_cases: Vec<WrongTestCase> = vec![];
        for _ in 0..num_tests {
            let p = make_random_problem(&mut rng);
            let result = check(&p);
            if let Some(wrong_test_case) = result {
                wrong_cases.push(wrong_test_case);
            }
            if wrong_cases.len() >= max_wrong_case {
                break;
            }
        }

        if !wrong_cases.is_empty() {
            for t in &wrong_cases {
                println!("{:?}", t.problem);
                println!("main ans : {:?}", t.main_ans);
                println!("naive ans: {:?}", t.naive_ans);
                println!();
            }
            println!("{} cases are wrong.", wrong_cases.len());
            panic!();
        }
    }
}

// ====== import ======
#[allow(unused_imports)]
use proconio::{
    derive_readable, fastout, input,
    marker::{Bytes, Chars, Usize1},
};
#[allow(unused_imports)]
use std::cmp::Reverse;
#[allow(unused_imports)]
use std::collections::{BinaryHeap, HashMap, HashSet};

// ====== output func ======
#[allow(unused_imports)]
use print_vec::*;
pub mod print_vec {

    use proconio::fastout;
    #[fastout]
    pub fn print_vec<T: std::fmt::Debug>(arr: &[T]) {
        for a in arr {
            println!("{:?}", a);
        }
    }
    #[fastout]
    pub fn print_vec_1line<T: std::fmt::Debug>(arr: &[T]) {
        let msg = arr
            .iter()
            .map(|x| format!("{:?}", x))
            .collect::<Vec<String>>()
            .join(" ");
        println!("{}", msg);
    }
    #[fastout]
    pub fn print_vec2<T: std::fmt::Debug>(arr: &Vec<Vec<T>>) {
        for row in arr {
            let msg = row
                .iter()
                .map(|x| format!("{:?}", x))
                .collect::<Vec<String>>()
                .join(" ");
            println!("{}", msg);
        }
    }
    pub fn print_bytes(bytes: &[u8]) {
        let msg = String::from_utf8(bytes.to_vec()).unwrap();
        println!("{}", msg);
    }
    pub fn print_chars(chars: &[char]) {
        let msg = chars.iter().collect::<String>();
        println!("{}", msg);
    }
    #[fastout]
    pub fn print_vec_bytes(vec_bytes: &[Vec<u8>]) {
        for row in vec_bytes {
            let msg = String::from_utf8(row.to_vec()).unwrap();
            println!("{}", msg);
        }
    }
}

#[allow(unused)]
fn print_yesno(ans: bool) {
    let msg = if ans { "Yes" } else { "No" };
    println!("{}", msg);
}

// ====== snippet ======
0