本サイトABC086C – Travelingへは以下から
問題：Traveling
シカのAtCoDeerくんは二次元平面上で旅行をしようとしています。 AtCoDeerくんの旅行プランでは、時刻 0 に 点 (0,0) を出発し、 1 以上 N 以下の各 i に対し、時刻 ti に 点 (xi,yi) を訪れる予定です。
AtCoDeerくんが時刻 t に 点 (x,y) にいる時、 時刻 t+1 には 点 (x+1,y), (x−1,y), (x,y+1), (x,y−1) のうちいずれかに存在することができます。 その場にとどまることは出来ないことに注意してください。 AtCoDeerくんの旅行プランが実行可能かどうか判定してください。
制約
- 1 ≤ N ≤ 105
- 0 ≤ x
i≤ 105 - 0 ≤ yi ≤ 105
- 1 ≤ ti ≤ 105
- ti < ti+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())
plans = []
for _ in range(N):
t, x, y = map(int, input().split())
plans.append((t, x, y))
# ========================
# 処理
# ========================
prev_time, prev_x, prev_y = 0, 0, 0
is_possible = True
for t, x, y in plans:
distance = abs(x - prev_x) + abs(y - prev_y)
time_difference = t - prev_time
if distance > time_difference or (time_difference - distance) % 2 != 0:
is_possible = False
break
prev_time, prev_x, prev_y = t, x, y
# ========================
# 出力
# ========================
if is_possible:
print("Yes")
else:
print("No")解説
入力
- 目的: 入力データをすべて受け取り、リスト
plansに格納する。 - リストの構造:
- 各要素
(t, x, y)は「時刻tと座標(x, y)」を意味します。
- 各要素
N = int(input())
plans = []
for _ in range(N):
t, x, y = map(int, input().split())
plans.append((t, x, y))処理
- 目的: 入力データを1つずつ確認し、移動が可能かどうか判定する。
- チェック内容:
- 移動距離が時間差より大きい場合 → 不可能
- 時間と移動距離の差が偶数でない場合 → 停止が不可能
prev_time, prev_x, prev_y = 0, 0, 0
is_possible = True
for t, x, y in plans:
distance = abs(x - prev_x) + abs(y - prev_y)
time_difference = t - prev_time
if distance > time_difference or (time_difference - distance) % 2 != 0:
is_possible = False
break
prev_time, prev_x, prev_y = t, x, y出力
- 判定結果に基づいて出力します。
is_possibleフラグがTrueなら Yes、そうでなければ No。
if is_possible:
print("Yes")
else:
print("No")まとめ
# ========================
# 入力
# ========================
# 旅行プランの数を入力
N = int(input())
# 各プラン（時刻と座標）をリストとして受け取る
plans = []
for _ in range(N):
t, x, y = map(int, input().split()) # 時刻 t と座標 (x, y)
plans.append((t, x, y)) # リストに追加
# ========================
# 処理
# ========================
# 初期位置と時刻
prev_time, prev_x, prev_y = 0, 0, 0 # 最初は (0, 0) で時間も 0
# 実行可能かどうか判定するフラグ
is_possible = True
# 各プランに対して移動が可能かチェック
for t, x, y in plans:
# 移動距離（マンハッタン距離）を計算
distance = abs(x - prev_x) + abs(y - prev_y)
time_difference = t - prev_time # 時間の差を計算
# 移動不可能な場合の条件
if distance > time_difference or (time_difference - distance) % 2 != 0:
is_possible = False # 移動不可能
break # 処理を終了
# 位置と時刻を更新
prev_time, prev_x, prev_y = t, x, y
# ========================
# 出力
# ========================
if is_possible:
print("Yes") # 実行可能
else:
print("No") # 実行不可能
あわせて読みたい
【python】input関数の使い方
python公式ドキュメントはこちら input 関数は、キーボードから入力を受け取る際に使用されます。この関数は文字列型の入力を返します。 基本的な書式 input([prompt]) …
あわせて読みたい
【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 # INPUT a = int(input…
コメント