Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

AtCoder Beginners Selectionをやった

AtCoder Beginners Selection - AtCoder

AtCoderが用意した「初心者はまず全部これを解くこと」的な問題集を全部解きました。なんと4時間かかりました。最後の最後に朦朧としていてミスを冒しましたが、初心者向けということもあり、さすがに簡単でした。

f:id:akiradeveloper529:20190307140429j:plain

ただ、本来なら3時間で出来たはず。なぜかというと、Coinsという問題で勘違いを冒して嵌ったからです。

ABC087B - Coins

私はこの問題は、十字路を進んでいく問題と同じに見えてしまい、結果としてDPに突き進んでしまい、結局実装がうまく出来ずサンプルが通らず苦戦してしまいました。

fn solve() {
    input! {
        a: usize,
        b: usize,
        c: usize,
        x: usize,
    };

    let max = 500 * 50 + 100 * 50 + 50 * 50;
    let mut dp = vec![0; max + 1];
    dp[0] = 1;

    let mut idx = VecDeque::new();
    for i in 0 .. dp.len() {
        if dp[i] > 0 { idx.push_front(i); }
    }
    for i in idx {
        for j in 1 .. a + 1 {
            let k = i + 500 * j;
            dp[k] += dp[i];
        }
    }

    let mut idx = VecDeque::new();
    for i in 0 .. dp.len() {
        if dp[i] > 0 { idx.push_front(i); }
    }
    for i in idx {
        for j in 1 .. b + 1 {
            let k = i + 100 * j;
            dp[k] += dp[i];
        }
    }

    let mut idx = VecDeque::new();
    for i in 0 .. dp.len() {
        if dp[i] > 0 { idx.push_front(i); }
    }
    for i in idx {
        for j in 1 .. c + 1 {
            let k = i + 50 * j;
            dp[k] += dp[i];
        }
    }

    println!("{}", dp[x]);
}

でも後になってから他の回答例を見ると愚直に三重ループを回して余裕で間に合っていました。多くて50なのだから当たり前ですね。あとは、今回はいらないと思いますが、全体を最大公約数の50で終わって数字を小さくしてる解答もありました。これは場合によっては使えるかもしれないですね。

嵌ってしまいましたが、DPの訓練にはなったので良かったことにします。

問題を解いていくに当たっては、たなこふさんが作った入力を読み取るためのマクロや、online-judge-toolsというツールがサンプルデータを作ったり実行するのにとても役立ちました。Rustで競プロをするためのツールが揃っていて助かります。