結果

問題 No.3329 Only the Rightest Choice is Right!!!
コンテスト
ユーザー elphe
提出日時 2025-10-25 11:58:56
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 138 ms / 1,571 ms
コード長 3,114 bytes
コンパイル時間 12,561 ms
コンパイル使用メモリ 400,240 KB
実行使用メモリ 142,848 KB
最終ジャッジ日時 2025-11-02 16:31:50
合計ジャッジ時間 19,077 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 74
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: variable `N` should have a snake case name
 --> src/main.rs:7:9
  |
7 |         N: usize,
  |         ^ help: convert the identifier to snake case: `n`
  |
  = note: `#[warn(non_snake_case)]` on by default

warning: variable `W` should have a snake case name
 --> src/main.rs:8:9
  |
8 |         W: usize,
  |         ^ help: convert the identifier to snake case (notice the capitalization): `w`

warning: variable `N` should have a snake case name
  --> src/main.rs:34:5
   |
34 |     N: usize,
   |     ^ help: convert the identifier to snake case: `n`

warning: variable `W` should have a snake case name
  --> src/main.rs:35:5
   |
35 |     W: usize,
   |     ^ help: convert the identifier to snake case (notice the capitalization): `w`

ソースコード

diff #
raw source code 

use proconio::{input, fastout};

#[fastout]
fn main() {
    // 入力読み取り
    input! {
        N: usize,
        W: usize,
        v: [u32; N],
        w: [usize; N],
    }

    // 動的計画法を実行して選ばれたアイテムの 1-based インデックス列を得る
    let ans = solve(N, W, &v, &w);

    // 出力（件数とインデックス列）
    println!("{}", ans.len());
    if !ans.is_empty() {
        // Vec<String> に変換してスペース区切りで出力
        let s = ans.iter().map(|x| x.to_string()).collect::<Vec<_>>().join(" ");
        println!("{}", s);
    } else {
        println!();
    }
}

// アルゴリズム本体
// - N: アイテム数
// - W: 重量上限（予算）
// - v: 利益配列（u32）
// - w: 重み配列（usize）
// 戻り値: 選ばれたアイテムの 1-based インデックス列
fn solve(
    N: usize,
    W: usize,
    v: &[u32],
    w: &[usize],
) -> Vec<u32> {
    // dp[i][j] = (最大利益, 次に進むためのインデックス)
    // 次インデックスは選択時に i+1 を格納してあり、選択が無ければ sentinel (usize::MAX)
    let sentinel = usize::MAX;
    // 初期化: サイズ (N+1) x (W+1)、すべて (0, sentinel)
    let mut dp: Vec<Vec<(u64, usize)>> = vec![vec![(0u64, sentinel); W + 1]; N + 1];

    // 後ろから遡って DP を構築
    for i in (0..N).rev() {
        let wi = w[i];
        let vi = v[i] as u64;
        // j < w[i] の場合は選べないのでそのままコピー
        for j in 0..wi.min(W + 1) {
            dp[i][j] = dp[i + 1][j];
        }
        // j >= w[i] の場合は選ぶか選ばないか比較
        for j in wi..=W {
            let without = dp[i + 1][j].0;
            let with = dp[i + 1][j - wi].0 + vi;
            // ご利益が等しいなら選ばない方が良い
            if without >= with {
                dp[i][j] = dp[i + 1][j];
            } else {
                // 選ぶ場合は利益と「次に進むインデックス」を格納（1-based 相当で i+1）
                dp[i][j] = (with, i + 1);
            }
        }
    }

    // トレースバック（遡及）パート
    let mut ans: Vec<u32> = Vec::new();
    let mut idx = dp[0][W].1; // ここには選択された最初のインデックス (i+1) が入るか sentinel
    let mut budget = W;
    while idx != sentinel {
        // dp に格納されている値は i+1（1-based 相当）なのでそのまま出力配列に追加
        // 型を u32 に合わせて変換
        ans.push(idx as u32);
        // 次の budget は現在選んだ要素の重みを引く（w は 0-based、かつ idx は i+1 なので idx-1 が元の i）
        let prev_i = idx - 1;
        // safety: prev_i は必ず N 未満であるはず（dp の構築論理に基づく）
        budget = budget.saturating_sub(w[prev_i]);
        // 次の idx を dp テーブルから取得（次の状態は dp[idx][budget].1）
        // dp の行インデックスは idx（i+1）でそのまま使える
        idx = dp[idx][budget].1;
    }

    ans
}
0