#3 - 文系出身エンジニアが競プロをやる

夜分遅くにこんばんは。
AtCoder beginners selectionの最後の問題を解きました。
なんか1時間以上かかった気がします。
C問題は結構壁を感じる…。時間かかったので詳細に書いていきます。

問題文

シカのAtCoDeerくんは二次元平面上で旅行をしようとしています。 AtCoDeerくんの旅行プランでは、時刻0に点 (0,0)を出発し、1以上N以下の各iに対し、時刻tに対し、時刻tiに点(xi,yi)を訪れる予定です。
AtCoDeerくんが時刻 tに 点 (x,y)にいる時、時刻 t+1には 点(x+1,y), (x−1,y), (x,y+1), (x,y−1)のうちいずれかに存在することができます。
その場にとどまることは出来ないことに注意してください。
AtCoDeerくんの旅行プランが実行可能かどうか判定してください。

入力

N
t1 x1 y1
t2 x2 y2
:
tN xN yN

出力

旅行プランが実行可能なら"Yes"を、不可能なら"No"を出力してください。

ABC086C - Traveling

#include <iostream>
#include <algorithm>

using namespace std;

int steps(int x, int y, int dx, int dy) {
    return (abs(x - dx) + abs(y - dy));
}

int main() {
    int N;
    cin >> N;

    bool answer = true;
    int t, x, y, dt, dx, dy;
    dt = dx = dy = 0;
    for (int i = 0; i < N; i++) {
        cin >> t >> x >> y;
        if ((t - dt) < steps(x, y, dx, dy)) {
            answer = false;
            break;
        }
        if (((t - dt) >= steps(x, y, dx, dy)) && ((t - dt) - steps(x, y, dx, dy)) % 2 == 1) {
            answer = false;
            break;
        }
        dt = t;
        dx = x;
        dy = y;
    }

    if (answer) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

GitHubにも置いてあります。

paveg/programming_contest

解き終わったあと、認識が薄かった部分について調べて知識を補強したのでメモとして残しておきます。

マンハッタン距離

幾何学における距離概念のひとつ。
各座標の差（の絶対値）の総和を2点間の距離とする。

幾何学における距離概念のひとつらしい…（知らなかった）
雰囲気で絶対値なんだろうなと思って、それらしい解答になっててよかった。

dt, dx, dyを前回との差分とすると

時刻(t - dt) < マンハッタン距離(abs(x - dx) + abs(y - dy))
は到達不能と判断できる。

そして
時刻(t - dt) >= マンハッタン距離(abs(x - dx) + abs(y - dy))
とするともし偶数であれば到達可能性が存在する感じかな。

仮に戻ってないのであれば奇数になるはず。

一時間ぐらいボーッとしていた記憶があります。
そして基本夜型なので朝方に切り替えたい気持ちはある…。

過去問をゴリゴリ解いていく予定なので、教本となる簡便な書籍をKindleで購入しました。もし興味がある方いましたら是非！

やっていくぞ💪