競技プログラミング

ABC086C – Traveling

https://atcoder.jp/contests/abs/tasks/arc089_a

この問題はAtCoDeer君が訪れる予定の各地点と時刻についての情報が与えられ、その旅行計画が可能かどうかを判断するものです。各地点への移動は、1時間あたり上下左右に1つずつ動くことができ、現在地にとどまることはできません。

問題を解くための手がかりは「マンハッタン距離」と「パリティ」です。

マンハッタン距離は、2次元格子上の2点間の最短距離で、格子上を移動する場合には最適な距離となります。この距離は、絶対値|x2 – x1| + |y2 – y1|で計算されます。

パリティはある値が偶数であるか奇数であるかを表す値で、ここではそれぞれの地点への時間とその地点のマンハッタン距離のパリティが一致するかどうかをチェックします。

ではSwiftでの実装を見てみましょう。

import Foundation

let N = Int(readLine()!)!
var txys = [[Int]]()
for _ in 0..<N {
    txys.append(readLine()!.split(separator: " ").map { Int($0)! })
}

txys.insert([0, 0, 0], at: 0)
var isPossible = true

for i in 0..<N {
    let dt = txys[i+1][0] - txys[i][0]
    let dist = abs(txys[i+1][1] - txys[i][1]) + abs(txys[i+1][2] - txys[i][2])
    if dt < dist || dt % 2 != dist % 2 {
        isPossible = false
    }
}

print(isPossible ? "Yes" : "No")

このコードでは、まず入力を読み取り、各地点と時刻の情報を2次元配列に格納します。そして、原点での初期状態を配列の先頭に追加します。

次に、旅行が可能かどうかをチェックするためのループを行います。各ステップでは、次の地点までの時間と距離を計算し、これらのパリティが一致するか、また次の地点への時間がその距離以上かどうかをチェックします。これらの条件のいずれかでも満たさない場合は、旅行は不可能と判断します。

最後に、旅行が可能かどうかの結果を出力します。

この問題のポイントは、マンハッタン距離とパリティの概念を理解し、それを問題の解法に適用することです。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です