ABC086C – Traveling解説　Atcoder Beginners Selection解いてみた

Atcoder

Atcoder

こんにちは、seiです！
今回はAtCoderの初心者向け問題集であるBeginners Selectionを解いてみたので、その中でも難易度が高めと言われているABC086C – Travelingについて解説したいと思います。

1 ABC086C – Travelingの概要
2 問題の解説
3 パリティとは
4 まとめ

ABC086C – Travelingの概要

この問題は、ある場所から別の場所に向かう移動が複数回ある場合、その移動を行えるかどうかを判断する問題です。条件は時刻tに(x, y)の位置にいるとき、時刻t+1には(x+1, y), (x-1, y), (x, y+1), (x, y-1)のどれかに移動することができます。つまり1だけ時間がたつと、上下左右どれか一方向に1進めるということです。
この問題は、偶奇について考えると解けます。パリティという概念があります。

問題の解説

早速解説です。以下はC++で書いた例です。

#include <iostream>
using namespace std;

int main()
{
    int n, x[110000] = {}, y[110000] = {}, t[110000] = {};
    bool result = true;

    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        cin >> t[i] >> x[i] >> y[i];
    }

    for (int i = 1; i <= n; i++)
    {
        int canMoveDistance = t[i] - t[i - 1];
        int dt = abs(x[i] - x[i - 1]) + abs(y[i] - y[i - 1]);

        if (dt > canMoveDistance)
        {
            result = false;
            break;
        }

        if (canMoveDistance % 2 != dt % 2)
        {
            result = false;
            break;
        }
    }
    if (result)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

変数の説明

nは旅行計画のステップ数を表します。
xとyは各ステップでの旅行者の位置を表します。
tは各ステップの時刻を表します。
resultは旅行者が目的地に到達可能かどうかを表します。

canMoveDistanceは、前のステップから現在のステップまでに旅行者が移動できる最大距離を表します。
dtは、これから旅行者が実際に移動する距離を表します。絶対値をとっています。

1.移動可能な距離より、実際に移動する距離のほうが長い場合は明らかにプラン失敗です。
2.移動可能距離（canMoveDistance）とdt（実際に移動する距離）の偶奇が一致していれば、その点に到達可能です。

ある点からある点に移動する際の距離の偶奇は決まっています。例えば初期値の(0,0)から(0,1)に(1,6)を通って移動する場合を考えてみます。最初に1+6=7移動して、そこから|1-0|+|6-1|=6移動します。この二つの距離を足して13になりますがこれは奇数です。どういう点を経由した経路でも合計距離は奇数になることが分かります。

パリティとは

パリティは、数値の偶奇性を表す言葉です。一般的に、ある数値が偶数であるか奇数であるかを表すときに用いられます。

パリティは、計算機科学や情報技術分野でも用いられているようです。たとえば、データ通信においては、送信するデータに対してパリティビットを追加することがあります。
パリティビットはデータ内の「1」の個数が偶数か奇数化の目印を付けて受け手側に送り、受け手側はデータ内の「1」の個数の偶奇とパリティビットの値が一致するかを確認します。
これにより、データが誤って転送された場合でも、受信側でエラーを検出することができます。