結果

問題 No.1515 Making Many Multiples
コンテスト
ユーザー LyricalMaestro
提出日時 2024-12-30 21:26:31
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 5,163 bytes
コンパイル時間 18,464 ms
コンパイル使用メモリ 379,280 KB
実行使用メモリ 50,248 KB
最終ジャッジ日時 2024-12-30 21:27:42
合計ジャッジ時間 66,841 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 TLE * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::collections::HashMap;
use std::io;

fn main() {
    // Python側で使われている -10^18 と同等の値
    const MIN_VALUE: i64 = -1_000_000_000_000_000_000;

    // --- 入力の受け取り ---
    // 1行目: N, K, X, Y
    let mut input_str = String::new();
    io::stdin().read_line(&mut input_str).unwrap();
    let mut it = input_str.split_whitespace();
    let _n: usize = it.next().unwrap().parse().unwrap();  // N (使わない場合でも受け取っておく)
    let k: usize = it.next().unwrap().parse().unwrap();   // K
    let x: i64 = it.next().unwrap().parse().unwrap();     // X
    let y: i64 = it.next().unwrap().parse().unwrap();     // Y

    // 2行目: A (長さ N の配列)
    input_str.clear();
    io::stdin().read_line(&mut input_str).unwrap();
    let a_list: Vec<i64> = input_str
        .split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect();

    // --- dp テーブルを準備 ---
    // Python: dp = [[MIN_VALUE] * K for _ in range(K)]
    let mut dp = vec![vec![MIN_VALUE; k]; k];

    // Python: dp[X % K][Y % K] = 0, dp[Y % K][X % K] = 0
    // ただし負の値で割るケースも考慮し、(x % k + k) % k のように安全に余りを取る
    let x_mod = ((x % k as i64) + k as i64) as usize % k;
    let y_mod = ((y % k as i64) + k as i64) as usize % k;
    dp[x_mod][y_mod] = 0;
    dp[y_mod][x_mod] = 0;

    // Python: max_dp_x, max_dp_y を準備
    let mut max_dp_x = vec![MIN_VALUE; k];
    let mut max_dp_y = vec![MIN_VALUE; k];

    // Python: max_dp_x[x] = max(dp[x][y] for y in range(K))
    for x_idx in 0..k {
        let mut m_value = MIN_VALUE;
        for y_idx in 0..k {
            m_value = m_value.max(dp[x_idx][y_idx]);
        }
        max_dp_x[x_idx] = m_value;
    }

    // Python: max_dp_y[y] = max(dp[x][y] for x in range(K))
    for y_idx in 0..k {
        let mut m_value = MIN_VALUE;
        for x_idx in 0..k {
            m_value = m_value.max(dp[x_idx][y_idx]);
        }
        max_dp_y[y_idx] = m_value;
    }

    // --- メインループ (A の各要素について更新) ---
    for &a in &a_list {
        // Python: a_ = a % K
        let a_ = ((a % k as i64) + k as i64) as usize % k;

        // 更新候補を一時的に保存する HashMap
        // Python: updates = {}
        let mut updates: HashMap<(usize, usize), i64> = HashMap::new();

        // 1) 結局 A を捨てるもの (Pythonコメントより)
        //    for k_y in range(K):
        //        k_x_ = (- a_ - k_y) % K
        //        updates[(k_x_, k_y)] = dp[k_x_][k_y] + 1
        for k_y in 0..k {
            let ky_i64 = k_y as i64;
            let kx_ = ((- (a % k as i64) - ky_i64) % k as i64 + k as i64) as usize % k;
            let new_val = dp[kx_][k_y] + 1;
            updates.insert((kx_, k_y), new_val);
        }

        // 2) for k_y in range(K):
        //       k_x_ = (- a_ - k_y) % K
        //       new_key = (a_, k_y)
        //       updates[new_key] = max(updates.get(new_key, dp[a_][k_y]),
        //                              dp[k_x_][k_y] + 1, max_dp_y[k_y])
        for k_y in 0..k {
            let ky_i64 = k_y as i64;
            let kx_ = ((- (a % k as i64) - ky_i64) % k as i64 + k as i64) as usize % k;
            let new_key = (a_, k_y);

            // すでに入っている値があれば取り出し、なければ dp[a_][k_y]
            let current_val = updates.get(&new_key).cloned().unwrap_or(dp[a_][k_y]);

            let candidate1 = dp[kx_][k_y] + 1;
            let candidate2 = max_dp_y[k_y];
            let new_val = current_val.max(candidate1).max(candidate2);

            updates.insert(new_key, new_val);
        }

        // 3) for k_x in range(K):
        //       k_y_ = (- a_ - k_x) % K
        //       new_key = (k_x, a_)
        //       updates[new_key] = max(updates.get(new_key, dp[k_x][a_]),
        //                              dp[k_x][k_y_] + 1, max_dp_x[k_x])
        for k_x in 0..k {
            let kx_i64 = k_x as i64;
            let ky_ = ((- (a % k as i64) - kx_i64) % k as i64 + k as i64) as usize % k;
            let new_key = (k_x, a_);

            let current_val = updates.get(&new_key).cloned().unwrap_or(dp[k_x][a_]);

            let candidate1 = dp[k_x][ky_] + 1;
            let candidate2 = max_dp_x[k_x];
            let new_val = current_val.max(candidate1).max(candidate2);

            updates.insert(new_key, new_val);
        }

        // 4) updates で計算した値を dp に反映しつつ max_dp_x / max_dp_y を更新
        for ((x_idx, y_idx), val) in updates {
            let updated_val = dp[x_idx][y_idx].max(val);
            dp[x_idx][y_idx] = updated_val;

            max_dp_x[x_idx] = max_dp_x[x_idx].max(updated_val);
            max_dp_y[y_idx] = max_dp_y[y_idx].max(updated_val);
        }
    }

    // --- 最終的な答えを探す ---
    // Python: answer = max(dp[x][y] for x in range(K) for y in range(K))
    let mut answer = MIN_VALUE;
    for x_idx in 0..k {
        for y_idx in 0..k {
            answer = answer.max(dp[x_idx][y_idx]);
        }
    }

    // 結果の出力
    println!("{}", answer);
}
0