ABC438 D – Tail of Snake

D - Tail of Snake

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

入力例１は以下のようになっている。

頭らしさ（A）・胴らしさ（B）・尾らしさ（C）の合計が最大になる分け方は、0〜１までをA、2 をB、3〜4までをCとすると16で最大になる。

DPのような考え方で最大を取っていくと答えが求められる。

スタートはA0=1。A0から選ぶことができるのは下の表の☆の部分（A1かB1）

括弧内はそれぞれ選んだ場合値の合計。

A0からCに行くことは制約上ない（Bは1以上選ばれるため）ので、続いてA1について考えると以下のようになる。

次にB1について考えると、ここで初めてA1+B2の値とB1＋B2の値がかぶることになるが、最初に書いた通り最大を採用すれば良く、A1+B2の9を採用する。

この要領で最後まで埋めていくとC4で答えがもとまる。

以下でACできました。（その他で気をつけるところは配列外参照のケアやDPの初期値を大きな値にしておくこと）

#[allow(unused_imports)]
use itertools::{iproduct, Itertools};
#[allow(unused_imports)]
use num_traits::pow;
#[allow(unused_imports)]
use proconio::{
    fastout, input,
    marker::{Chars, Usize1},
};
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::iter::FromIterator;

fn main() {
    input! {
        n: usize,
        a: [i64; n],
        b: [i64; n],
        c: [i64; n],
    }
    let abc = vec![a, b, c];
    let mut dp = vec![vec![i64::MIN; 3]; n];
    dp[0][0] = abc[0][0];
    for i in 0..n - 1 {
        for j in 0..3 {
            if dp[i][j] == i64::MIN {
                continue;
            }
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + abc[j][i + 1]);
            if j == 2 {
                continue;
            }
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + abc[j + 1][i + 1]);
        }
    }
    println!("{}", dp[n - 1][2]);
}Code language: Rust (rust)

今回制約上マイナスが出ることはないのでDPの初期値を−1でも良いと考えていましたが、それではACできませんでした。

原因としては-1(i32)では入力値が大きい場合にオーバーフローしてマイナスの値になってしまい、計算がおかしくなってしまうという理解です。（このあたり間違っていたらコメントいただきたい、、、）

なのでこういう大きい値を使う際はサイズに応じてi64などを使うと良いというのは今回の学びでした。