AtCoder Beginners Selection　ABC086C – Travelingをpythonで解いてみた

本サイトABC086C – Travelingへは以下から

問題：Traveling

シカのAtCoDeerくんは二次元平面上で旅行をしようとしています。 AtCoDeerくんの旅行プランでは、時刻 0 に 点 (0,0) を出発し、 1 以上 N 以下の各 i に対し、時刻 t_i に 点 (x_i,y_i) を訪れる予定です。

AtCoDeerくんが時刻 t に 点 (x,y) にいる時、 時刻 t+1 には 点 (x+1,y), (x−1,y), (x,y+1), (x,y−1) のうちいずれかに存在することができます。 その場にとどまることは出来ないことに注意してください。 AtCoDeerくんの旅行プランが実行可能かどうか判定してください。

制約

• 1 ≤ N ≤ 10⁵
• 0 ≤ x_i ≤ 10⁵
• 0 ≤ y_i ≤ 10⁵
• 1 ≤ t_i ≤ 10⁵
• t_i < t_i+1 (1 ≤ i ≤ N−1)
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
t1 x1 y1
t2 x2 y2
:
tN xN yN

出力

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

入力例 1

2
3 1 2
6 1 1

出力例 1

Yes

例えば、(0,0), (0,1), (1,1), (1,2), (1,1), (1,0), (1,1) と移動すればよいです。

入力例 2

1
2 100 100

出力例 2

No

(0,0) にいる状態から 2 秒後に (100,100) にいるのは不可能です。

入力例 3

2
5 1 1
100 1 1

出力例 3

No

解答例

N = int(input())
prev_t, prev_x, prev_y = 0, 0, 0

for _ in range(N):
    t, x, y = map(int, input().split())
    dist = abs(x - prev_x) + abs(y - prev_y)
    time_diff = t - prev_t

    if dist > time_diff or (time_diff - dist) % 2 != 0:
        print("No")
        exit()

    prev_t, prev_x, prev_y = t, x, y

print("Yes")

解説

この問題は、与えられた移動計画が実行可能かどうかを判定するものです。具体的には、各移動が制約内で可能かどうかを確認します。

以下の手順で問題を解くことができます。

• 入力の受け取り:
  • N(移動の回数)を入力として受け取ります。
  • 各移動に関する情報(時刻、x座標、y座標)をN回受け取ります。
• 初期設定:
  • 移動の開始地点は座標(0, 0)とします。
  • 移動の開始時刻も0とします。
• 移動の確認:
  • 各移動ごとに、以下の手順を実行します： a. 移動に必要な時間と、実際に移動する距離を計算します。 b. 移動距離が指定された時間内に到達可能かどうかを確認します。具体的には、移動にかかる時間が与えられた時間より短いか、または移動時間と移動距離の奇数・偶数の関係が一致しない場合、その移動は不可能と判断します。 c. 移動が可能であれば、次の移動のために現在の位置と時刻を更新します。
• 結果の出力:
  • すべての移動が可能であれば、”Yes”を出力します。
  • 一つでも不可能な移動があれば、”No”を出力します。

以下は、この手順をPythonで実装したコードの例です。

# 入力される移動の回数を取得
N = int(input())

# 前回の時刻、x座標、y座標を初期化(最初はすべて0)
prev_t, prev_x, prev_y = 0, 0, 0

# N回の移動についての情報を順番に処理
for _ in range(N):
    # 時刻t、x座標、y座標を入力
    t, x, y = map(int, input().split())

    # 前回の位置からの移動距離を計算
    dist = abs(x - prev_x) + abs(y - prev_y)
    
    # 前回からの経過時間を計算
    time_diff = t - prev_t

    # 移動が可能かどうかのチェック
    # 移動距離が経過時間よりも大きい、または経過時間と移動距離の差が奇数の場合、移動は不可能
    if dist > time_diff or (time_diff - dist) % 2 != 0:
        print("No")
        exit()  # プログラムを終了

    # 次のループのために、現在の時刻、x座標、y座標を更新
    prev_t, prev_x, prev_y = t, x, y

# すべての移動が可能であれば"Yes"を出力
print("Yes")

あわせて読みたい

【python】input関数の使い方 python公式ドキュメントはこちら Pythonで用意されている組み込み関数の input 関数の使い方です。キーボードから入力した文字や数値を受け取る際に使用します。 input …

あわせて読みたい

【python】for文の使い方 python公式ドキュメントはこちら Python の for 文は、 C 言語や Pascal 言語での for 文とは少し異なり、任意のシーケンス型 (リストまたは文字列) にわたって反復を行…

あわせて読みたい

【python】if文の使い方 python公式ドキュメントはこちら if 文は条件分岐をおこなうための文法です。Pythonのif文は、一般的な他のプログラミング言語と同様に、条件式の結果が真(true)である…

あわせて読みたい

【python】print関数の使い方 python公式ドキュメントはこちら Pythonで用意されている組み込み関数の中の print 関数の使い方です。引数に指定した文字列や数値、変数に格納された値などを標準出力…

前の問題へ

あわせて読みたい

AtCoder Beginners Selection　ABC049C – 白昼夢をpythonで解いてみた 本サイトABC049C – 白昼夢へは以下から 問題：白昼夢 英小文字からなる文字列 S が与えられます。 Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すこと…

一覧へ

あわせて読みたい

AtCoder Beginners Selection 11問をpythonで解いてみた AtCoderの初心者向け問題集である AtCoder Beginners Selection の11問をPythonで解説します。 AtCoder Beginners Selection Welcome to AtCoder a = int(input()) b, c…