結果

問題 No.3391 Line up Dominoes
コンテスト
ユーザー LyricalMaestro
提出日時 2025-12-06 00:43:29
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 2,337 ms / 3,000 ms
コード長 2,021 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 13,656 ms
コンパイル使用メモリ 398,228 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-12-06 00:44:14
合計ジャッジ時間 42,252 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use std::collections::HashMap;
use std::io::{self, Read};

const MOD: i64 = 998244353;

fn main() {
    // ---- read all ----
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let mut it = input.split_whitespace();

    let n: usize = it.next().unwrap().parse().unwrap();
    let m: usize = it.next().unwrap().parse().unwrap();
    let k: i64 = it.next().unwrap().parse().unwrap();

    let mut a_map: HashMap<i64, i64> = HashMap::new();
    for _ in 0..n {
        let a: i64 = it.next().unwrap().parse().unwrap();
        *a_map.entry(a).or_insert(0) += 1;
    }

    // 座標圧縮
    let mut value_list: Vec<i64> = a_map.keys().cloned().collect();
    value_list.sort();
    let value_max = value_list.len();

    // dp 初期化
    let mut dp = vec![0i64; value_max];
    let mut base = vec![0i64; value_max];

    for (i, &v) in value_list.iter().enumerate() {
        let c = a_map[&v] % MOD;
        dp[i] = c;
        base[i] = c;
    }

    // 第二バッファ
    let mut ndp = vec![0i64; value_max];

    // M 回遷移
    for _step in 1..m {
        let mut low = 0usize;
        let mut high = 0usize;

        let mut cum_d = dp[0];

        for i in 0..value_max {
            let a0 = value_list[i];

            // low を進める
            while low < i && a0 - value_list[low] > k {
                cum_d = (cum_d - dp[low]) % MOD;
                if cum_d < 0 {
                    cum_d += MOD;
                }
                low += 1;
            }

            // high を進める
            while high + 1 < value_max && value_list[high + 1] <= a0 + k {
                high += 1;
                cum_d = (cum_d + dp[high]) % MOD;
            }

            ndp[i] = (cum_d * base[i]) % MOD;
        }

        // バッファを swap して次ループへ
        std::mem::swap(&mut dp, &mut ndp);
    }

    // 最終結果
    let mut ans = 0i64;
    for v in dp.iter() {
        ans = (ans + v) % MOD;
    }
    println!("{}", ans);
}
0