こんにちは!サトシです!
この記事では、「AtCoderに登録して最初に解くべき10問(AtCoder Beginners Selection)」の10問目「Traveling」をめちゃくちゃ分かりやすく解説していきます。
AtCoder で問題を解くためには、新規登録しないといけません。
新規登録はこちらから → AtCoder に新規登録する
それでは、「Traveling」の解説をしていきます!

10問目「Traveling」で身につくスキル
この問題では、こんなスキルが身につきます。
- 「_」の使い方
先に、これがどのようなスキルなのかを説明します。
「_」の使い方
「_」(アンダースコア)は、ゴミ箱のように使うことができます。
例えば、「”Hello”と10回表示したい」というときは下のように書きます。
for i in range(10):
print('Hello')
でも、この「i」って変数、結局使わないですよね?
こういうときに、「_」を使います。
for _ in range(10):
print('Hello')
このように「_」を使うと、下の2つのメリットがあります。
- メモリを余計に使わないで済む
- 使わない変数であることが一目でわかる
10問目「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
・1 ≤ xi ≤ 105
・1 ≤ yi ≤ 105
・1 ≤ ti ≤ 105
・ti ≤ ti+1 ( 1 ≤ i ≤ N – 1 )
・入力は全て整数入力
入力は以下の形式で標準入力から与えられる。N
t1 x1 y1
t2 x2 y2
.
.
tN xN yN出力
旅行プランが実行可能なら ‘Yes’ を、不可能なら ‘No’ を出力してください。
入力例と出力例
入力例
2
2 0 2
3 1 2
出力例
Yes
2秒後に(0 , 2)、3秒後に(1 , 2)に行くことは可能なので、「Yes」と出力します。
解答例
for _ in range(int(input())):
t, x, y = map(int, input().split())
if (x + y + t) % 2 or (x + y) > t:
print('No')
exit(0)
print('Yes')
解説
下のように計算していきます。
- (0 , 0)から2回移動して(0 , 2)に行けるか
- (0 , 0)から3回移動して(1 , 2)に行けるか
- …
- (0 , 0)からt回移動して(x , y)に行けるか
また、t回移動して(x , y)に行けるのは、下の2つの条件を守っているときだけです。
- 「tが奇数なら、x+yが奇数」、「tが偶数なら、x+yが偶数」であること
- 「t > x+y」であること
では、コードを詳しく解説していきます。
上の手順で説明した通り、「(0 , 0)からt回移動して、(x , y)に行けるか」をN回確認しないといけません。
なので、プログラム全体をN回ループさせます。
for _ in range(int(input())):
入力を受け取ります。
t, x, y = map(int, input().split())
先ほどの条件を守れていないときは、「No」と出力して、プログラムを終了します。
if (x + y + t) % 2 or (x + y) > t:
print('No')
exit(0)
「Yes」と出力します。
※もし守れていない条件があったら、すでにプログラムが終了しているはずなので、このプログラム「print(‘Yes’)」は実行されません。
print('Yes')
まとめとして、もう一度プログラムを確認してみましょう。
for _ in range(int(input())):
t, x, y = map(int, input().split())
if (x + y + t) % 2 or (x + y) > t:
print('No')
exit(0)
print('Yes')
これで「(0 , 0)からt回移動して(x , y)に行けるか」を調べることができました。
まとめ
ついに「AtCoder Beginners Selection」の10問を解くことができました!
この10問で身につけたスキルを使って、どんどん問題を解いていきましょう!
他の問題の解き方も知りたい方は下の記事をお読みください。
もし分からない点などありましたら、気軽にTwitterやコメントなどでご質問ください^^
少しでも参考になれば嬉しいです!