結果

問題 No.4 おもりと天秤
コンテスト
ユーザー cm-kojimat
提出日時 2020-10-29 16:34:43
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 2,522 bytes
コンパイル時間 14,915 ms
コンパイル使用メモリ 380,412 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-21 22:34:48
合計ジャッジ時間 14,485 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::io::{stdin, Read, StdinLock};
use std::str::FromStr;

struct Input {
    n: usize,
    w: Vec<usize>,
}

fn read_input(cin_lock: &mut StdinLock) -> Input {
    let n = next_token(cin_lock);
    let w = (0..n).map(|_| next_token(cin_lock)).collect();
    Input { n, w }
}

fn solve(input: Input) -> bool {
    let max_w: usize = input.w.iter().sum::<usize>();
    if max_w % 2 != 0 {
        return false;
    }

    let half_w = max_w / 2;
    let mut dp = vec![vec![false; half_w + 1]; 2];
    dp[0][0] = true; // 合計 0 になる組み合わせは存在する

    // 全ての重りに対して操作する
    for i in 0..input.n {
        let curr_line = i % 2; // 0, 1, 0, ...
        let next_line = (i + 1) % 2; // 1, 0, 1, ...

        // 存在しうる重りを考慮する
        for w in 0..half_w + 1 {
            dp[next_line][w] = if w < input.w[i] {
                // 前回の状態を引き継ぐ
                dp[curr_line][w]
            } else {
                // 選択した組み合わせが存在するかどうか
                dp[curr_line][w - input.w[i]]
            }
        }

        // すでに組み合わせが決まっている場合
        if dp[next_line][half_w] {
            return true;
        }
    }

    // 指定した重さの組み合わせがあるか判定
    return dp[input.n % 2][half_w];
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_solve() {
        assert_eq!(
            solve(Input {
                n: 3,
                w: vec![1, 2, 3],
            }),
            true
        );
        assert_eq!(
            solve(Input {
                n: 5,
                w: vec![1, 2, 3, 4, 5],
            }),
            false
        );
        assert_eq!(
            solve(Input {
                n: 15,
                w: vec![62, 8, 90, 2, 24, 62, 38, 64, 76, 60, 30, 76, 80, 74, 72],
            }),
            false
        );
    }
}

fn next_token<T: FromStr>(cin_lock: &mut StdinLock) -> T {
    cin_lock
        .by_ref()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>()
        .parse::<T>()
        .ok()
        .unwrap()
}

fn main() {
    let cin = stdin();
    let mut cin_lock = cin.lock();
    let input = read_input(&mut cin_lock);

    println!(
        "{}",
        if solve(input) {
            "possible"
        } else {
            "impossible"
        }
    );
}
0