Traveling [AtCoder Regular Contest 089 / AtCoder Beginner Contest 086 C]

https://beta.atcoder.jp/contests/arc089/tasks/arc089_a

解法

https://beta.atcoder.jp/contests/arc089/submissions/1998689

各区間について独立に実現可能か考える。
(px, py)から(X[i], Y[i])へ時間ptから時間T[i]で遷移可能かを判定する。
2つの座標を距離dは
d = abs(px - X[i]) + abs(py - Y[i])
である。これは移動は上下左右でしか行えないため、マンハッタン距離を距離とする。
使える時間dtは
dt = T[i] - pt
である。
　
まず自明なこととしてdt < dであるなら実現不可能である。
最短距離で移動しても間に合わないためである。
　
あとは、その場にとどまらずに移動できるかであるが、「dt - dが偶数であるなら移動できる」と言える。
詳しく言うと

• 最短距離で移動した後に使える時間がdt-d
• 目標の座標を右へ1つ移動->左へ1つ移動で目標の座標に戻るという動作で時間の調整ができる
• この時間の調整で目標の座標に最後にとどまれるのはdt-dが偶数のときだけ

　
各区間で実現可能性を確かめて、全て実現可能ならYes
1つでも実現不可能ならNo

int N, T[101010], X[101010], Y[101010];
//---------------------------------------------------------------------------------------------------
#define yes "Yes"
#define no "No"
string solve() {
    int pt = 0, px = 0, py = 0;
    rep(i, 0, N) {
        int d = abs(px - X[i]) + abs(py - Y[i]);
        int dt = T[i] - pt;
        if (dt < d) return no;
        if ((dt - d) % 2 == 1) return no;
 
        pt = T[i];
        px = X[i];
        py = Y[i];
    }
    return yes;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> T[i] >> X[i] >> Y[i];
    cout << solve() << endl;
}