結果

問題 No.1515 Making Many Multiples
コンテスト
ユーザー LyricalMaestro
提出日時 2024-12-30 21:49:38
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1,457 ms / 2,000 ms
コード長 4,617 bytes
コンパイル時間 16,655 ms
コンパイル使用メモリ 379,772 KB
実行使用メモリ 64,640 KB
最終ジャッジ日時 2024-12-30 21:50:54
合計ジャッジ時間 35,882 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::io;

fn main() {
    // Pythonコードの MIN_VALUE に対応
    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 の要素)
    input_str.clear();
    io::stdin().read_line(&mut input_str).unwrap();
    let a_list: Vec<i64> = input_str
        .split_whitespace()
        .map(|s| s.parse().unwrap())
        .collect();
    assert_eq!(a_list.len(), n);

    // dp, update_dp を 2次元配列で確保 (初期値は MIN_VALUE)
    let mut dp = vec![vec![MIN_VALUE; k]; k];
    let mut update_dp = vec![vec![MIN_VALUE; k]; k];

    // X%K, Y%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
    dp[x_mod][y_mod] = 0;
    dp[y_mod][x_mod] = 0;

    // max_dp_x, max_dp_y を定義（初期値はすべて MIN_VALUE）
    let mut max_dp_x = vec![MIN_VALUE; k];
    let mut max_dp_y = vec![MIN_VALUE; k];
    // Python同様、X%K, Y%K の位置は 0 で初期化
    max_dp_x[x_mod] = 0;
    max_dp_x[y_mod] = 0;
    max_dp_y[x_mod] = 0;
    max_dp_y[y_mod] = 0;

    // Pythonコードの answer (とりあえず i64 で扱う)
    let mut answer: i64 = 0;

    // --- A の各要素ごとにループ ---
    for &a in &a_list {
        // a_ = a % K (負対策込み)
        let a_ = ((a % k as i64) + k as i64) as usize % k;

        // Python でいう array = [] (更新対象の (x,y) を一時保存するベクタ)
        let mut update_pairs = Vec::new();

        // 1) 結局 A を捨てるもの
        //    for k_y in range(K):
        //        k_x_ = (-a_ - k_y) % K
        //        update_dp[k_x_][k_y] = dp[k_x_][k_y] + 1
        //        array.append((k_x_, k_y))
        for k_y in 0..k {
            let ky_i64 = k_y as i64;
            let a_i64 = a_ as i64; 
            let kx_ = (((-a_i64) - ky_i64) % (k as i64) + k as i64) as usize % k;

            update_dp[kx_][k_y] = dp[kx_][k_y].saturating_add(1);
            update_pairs.push((kx_, k_y));
        }

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

            // 4つの候補の最大をとる
            let candidate = update_dp[a_][k_y]
                .max(dp[a_][k_y])
                .max(dp[kx_][k_y].saturating_add(1))
                .max(max_dp_y[k_y]);

            update_dp[a_][k_y] = candidate;
            update_pairs.push((a_, k_y));
        }

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

            let candidate = update_dp[k_x][a_]
                .max(dp[k_x][a_])
                .max(dp[k_x][ky_].saturating_add(1))
                .max(max_dp_x[k_x]);

            update_dp[k_x][a_] = candidate;
            update_pairs.push((k_x, a_));
        }

        // 4) 更新を dp に反映 + max_dp_x, max_dp_y, answer を更新
        for (xx, yy) in update_pairs {
            if dp[xx][yy] < update_dp[xx][yy] {
                dp[xx][yy] = dp[xx][yy].max(update_dp[xx][yy]);
                max_dp_x[xx] = max_dp_x[xx].max(dp[xx][yy]);
                max_dp_y[yy] = max_dp_y[yy].max(dp[xx][yy]);
                answer = answer.max(dp[xx][yy]);
            }
            // update_dp をリセット
            update_dp[xx][yy] = MIN_VALUE;
        }
    }

    // Python での print(answer) に対応
    println!("{}", answer);
}
0