Atcoder ABS ABC086C Traveling

こんにちは、ナナオです。

前回に引き続き競プロを実施していきたいと思います。

今回の問題は以下です。

ABC086C - Traveling

実装

まずは単純に考えてみます。

まず条件のひとつ目として、時間内に移動できる距離は時間内に収まっている必要があります。

移動距離は「移動前のx座標と移動後のx座標の差」と「移動前のy座標と移動後のy座標の差」を足し合わせれば計算できます。

この「移動距離」が「移動前の時間と移動後の時間の差」の中に収まっているかどうかを判定する必要があります。

次に条件の二つ目として、先ほどの「移動距離」と「移動前の時間と移動後の時間の差」の奇数偶数判定が一致している必要があります。

これは単純で、例えば以下のようなケースを考えてみます。

2
1 1 0
3 1 0

このケースでは時間が1のときと時間が3のときの場所が全く同じです。

この場合条件の一つ目は満たしていますが、動き方としてはどうなるでしょうか？

…一回違う場所に行って戻ればこの動きは実現しそうですね。

ということは、条件1を満たしている場合で時間に余りがある場合は「行って」「戻る」という挙動ができるのであればよさそうですね。

さて、論よりコードということで以下のように実装しました。

use proconio::input;

fn main() {
    input! {
        n: usize,
        data: [(i16, i16, i16); n],
    };
    let (mut c, mut sy, mut sx) = (0, 0, 0);
    for i in 0..n {
        let (t, x, y) = data[i];
        let dd = (x - sx).abs() + (y - sy).abs();
        let dt = t - c;
        if dd > dt || dt % 2 != dd % 2 {
            println!("No");
            return;
        }
        sy = y;
        sx = x;
        c = t;
    }
    println!("Yes");
}

これだとうまく通りませんでした。なんだかまた値のオーバーフローが起こってしまったようなので、dataの値定義を変更しました。

use proconio::input;

fn main() {
    input! {
        n: usize,
        data: [(i32, i32, i32); n],
    };
    let (mut c, mut sy, mut sx) = (0, 0, 0);
    for i in 0..n {
        let (t, x, y) = data[i];
        let dd = (x - sx).abs() + (y - sy).abs();
        let dt = t - c;
        if dd > dt || dt % 2 != dd % 2 {
            println!("No");
            return;
        }
        sy = y;
        sx = x;
        c = t;
    }
    println!("Yes");
}

これで動きました。

ということで今回はこれで👍

実装#

実装