結果

問題 No.260 世界のなんとか3
ユーザー uAutDnLD5Pe5QqVuAutDnLD5Pe5QqV
提出日時 2019-02-05 21:24:33
言語 Rust
(1.77.0)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 7,308 bytes
コンパイル時間 3,406 ms
コンパイル使用メモリ 157,044 KB
実行使用メモリ 65,860 KB
最終ジャッジ日時 2023-08-30 23:56:40
合計ジャッジ時間 7,324 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 MLE -
testcase_04 MLE -
testcase_05 AC 47 ms
25,116 KB
testcase_06 AC 25 ms
16,960 KB
testcase_07 AC 116 ms
56,284 KB
testcase_08 AC 96 ms
57,060 KB
testcase_09 AC 55 ms
29,140 KB
testcase_10 AC 105 ms
51,052 KB
testcase_11 AC 124 ms
60,296 KB
testcase_12 AC 78 ms
46,340 KB
testcase_13 AC 14 ms
10,432 KB
testcase_14 AC 99 ms
56,864 KB
testcase_15 AC 20 ms
13,824 KB
testcase_16 AC 77 ms
46,060 KB
testcase_17 AC 69 ms
34,680 KB
testcase_18 AC 59 ms
30,724 KB
testcase_19 AC 96 ms
56,648 KB
testcase_20 AC 71 ms
35,936 KB
testcase_21 AC 66 ms
39,564 KB
testcase_22 AC 81 ms
47,652 KB
testcase_23 AC 7 ms
6,024 KB
testcase_24 AC 88 ms
52,076 KB
testcase_25 MLE -
testcase_26 MLE -
testcase_27 AC 1 ms
4,376 KB
testcase_28 MLE -
testcase_29 MLE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: variable does not need to be mutable
  --> Main.rs:81:5
   |
81 |     mut eight_remainder: usize,
   |     ----^^^^^^^^^^^^^^^
   |     |
   |     help: remove this `mut`
   |
   = note: `#[warn(unused_mut)]` on by default

warning: 1 warning emitted

ソースコード

diff # 

use std::io::BufRead;

pub struct StdinReader<R: BufRead> {
    pub buf_reader: R,
    pub buf: String,
}
impl<R: BufRead> StdinReader<R> {
    pub fn new(r: R) -> Self {
        StdinReader {
            buf_reader: r,
            buf: String::with_capacity(10000),
        }
    }
}

#[macro_export]
macro_rules! input {
    ($reader : expr, $t : ty) => { // one variable
        match &mut $reader {
            reader => {
                use std::io::BufRead;
                reader.buf_reader.read_line(&mut reader.buf).unwrap();
                let tmp_var: $t = reader.buf.trim().parse().unwrap(); 
                reader.buf.clear();
                tmp_var
            },
        }
    };
    ($reader : expr, $t0 : ty, $t1 : ty) => { // 2 tuple
        match &mut $reader {
            reader => {
                use std::io::BufRead;
                reader.buf_reader.read_line(&mut reader.buf).unwrap();
                let tmp_var: Vec<$t0> = reader.buf.trim().split_whitespace().map(|a| a.parse().unwrap()).collect();
                reader.buf.clear();
                (tmp_var[0].clone(), tmp_var[1].clone())
            }
        }
    };
    ($reader : expr, $t0 : ty, $t1 : ty, $t2 : ty) => { // 3 tuple
        match &mut $reader {
            reader => {
                use std::io::BufRead;
                reader.buf_reader.read_line(&mut reader.buf).unwrap();
                let tmp_var: Vec<$t0> = reader.buf.trim().split_whitespace().map(|a| a.parse().unwrap()).collect();
                reader.buf.clear();
                (tmp_var[0], tmp_var[1], tmp_var[2])
            }
        }
    };
    ($reader : expr, $t : ty; $size : expr) => { // Vector
        match &mut $reader {
            reader => {
                use std::io::BufRead;
                reader.buf_reader.read_line(&mut reader.buf).unwrap();
                let tmp_var: $t = reader.buf.trim().split_whitespace().map(|a| a.parse().unwrap()).collect();
                reader.buf.clear();
                tmp_var
            }
        }
    };
}

type Memo = Vec<Vec<Vec<Vec<Vec<Option<usize>>>>>>;

fn main() {
    let handle = std::io::stdin();
    let mut r = StdinReader::new(handle.lock());

    let (a_str, b_str): (String, String) = input!(r, String, String);
    let (a, b): (Vec<char>, Vec<char>) = (a_str.chars().collect(), b_str.chars().collect());

    // now_digit -> eight mod -> three mod -> is there three -> strict (lower || upper || lower && upper || all ok)
    let mut memo: Memo = vec![vec![vec![vec![vec![None; 4]; 2]; 3]; 8]; b.len()];
    println!("{}", dp(b.len() - 1, 0, 0, 0, 2, &a, &b, &mut memo));
}

const STRICT: usize = 1000000007;
fn dp(
    now_d: usize,
    mut eight_remainder: usize,
    three_remainder: usize,
    exist_three: usize,
    state: usize,
    a: &Vec<char>,
    b: &Vec<char>,
    memo: &mut Memo
) -> usize {
    if let Some(ans) = memo[now_d][eight_remainder][three_remainder][exist_three][state] {
        return ans;
    }

    let mut ans = 0;
    let a_n: usize = a.iter().rev().nth(now_d).unwrap_or(&'0').to_digit(10).unwrap() as usize;
    let b_n: usize = b.iter().rev().nth(now_d).unwrap().to_digit(10).unwrap() as usize;
    let mut lower = 0;
    let mut upper = 10; // not include
    if state == 0 {
        lower = a_n;
    } else if state == 1 {
        upper = b_n + 1;
    } else if state == 2 {
        lower = a_n;
        upper = b_n + 1;
    } else if state == 3 {
        // all ok
        // do nothing    
    } else { panic!("I dont know state{}!!!", state); }
    if now_d == 0 {
        ans += (lower..upper).into_iter().filter(
            |i| (exist_three == 1 || *i == 3 || (three_remainder + (i % 3)) % 3 == 0) && (eight_remainder + (i % 8)) % 8 != 0
        ).count();
        ans %= STRICT;
    } else {
        if state == 0 {
            for i in lower..upper {
                let mut now_eight_remainder = eight_remainder;
                if now_d < 3 {
                    now_eight_remainder += i * (10 as usize).pow(now_d as u32);
                    now_eight_remainder %= 8;
                }
                let now_exist_three = if exist_three == 1 || i == 3 { 1 } else { 0 };
                if i == a_n {
                    ans += dp(now_d-1, now_eight_remainder, (three_remainder + (i % 3)) % 3, now_exist_three, 0, a, b, memo);
                    ans %= STRICT;
                } else {
                    ans += dp(now_d-1, now_eight_remainder, (three_remainder + (i % 3)) % 3, now_exist_three, 3, a, b, memo);
                    ans %= STRICT;
                }
            }
        } else if state == 1 {
            for i in lower..upper {
                let mut now_eight_remainder = eight_remainder;
                if now_d < 3 {
                    now_eight_remainder += i * (10 as usize).pow(now_d as u32);
                    now_eight_remainder %= 8;
                }
                let now_exist_three = if exist_three == 1 || i == 3 { 1 } else { 0 };
                if i == b_n {
                    ans += dp(now_d-1, now_eight_remainder, (three_remainder + (i % 3)) % 3, now_exist_three, 1, a, b, memo);
                    ans %= STRICT;
                } else {
                    ans += dp(now_d-1, now_eight_remainder, (three_remainder + (i % 3)) % 3, now_exist_three, 3, a, b, memo);
                    ans %= STRICT;
                }
            }
        } else if state == 2 {
            for i in lower..upper {
                let mut now_eight_remainder = eight_remainder;
                if now_d < 3 {
                    now_eight_remainder += i * (10 as usize).pow(now_d as u32);
                    now_eight_remainder %= 8;
                }
                let now_exist_three = if exist_three == 1 || i == 3 { 1 } else { 0 };
                if a_n == b_n {
                    ans += dp(now_d-1, now_eight_remainder, (three_remainder + (i % 3)) % 3, now_exist_three, 2, a, b, memo);
                    ans %= STRICT;
                } else if i == a_n {
                    ans += dp(now_d-1, now_eight_remainder, (three_remainder + (i % 3)) % 3, now_exist_three, 0, a, b, memo);
                    ans %= STRICT;
                } else if i == b_n {
                    ans += dp(now_d-1, now_eight_remainder, (three_remainder + (i % 3)) % 3, now_exist_three, 1, a, b, memo);
                    ans %= STRICT;
                } else {
                    ans += dp(now_d-1, now_eight_remainder, (three_remainder + (i % 3)) % 3, now_exist_three, 3, a, b, memo);
                    ans %= STRICT;
                }
            }
        } else if state == 3 {
            for i in lower..upper {
                let mut now_eight_remainder = eight_remainder;
                if now_d < 3 {
                    now_eight_remainder += i * (10 as usize).pow(now_d as u32);
                    now_eight_remainder %= 8;
                }
                let now_exist_three = if exist_three == 1 || i == 3 { 1 } else { 0 };
                ans += dp(now_d-1, now_eight_remainder, (three_remainder + (i % 3)) % 3, now_exist_three, 3, a, b, memo);
                ans %= STRICT;
            }
        } else { panic!("I dont know state{}!!!", state); }
    }

    memo[now_d][eight_remainder][three_remainder][exist_three][state] = Some(ans);
    return ans;
}
0