【超初心者向け】AtCoderで最初に解くべき過去問集を分かりやすく解説します【１０問目】

こんにちは！サトシです！

 

この記事では、「AtCoderに登録して最初に解くべき１０問（AtCoder Beginners Selection）」の１０問目「Traveling」をめちゃくちゃ分かりやすく解説していきます。

 

それでは、「Traveling」の解説をしていきます！

【競プロ】最初に解くべき過去問１０問をPythonで分かりやすく解説します！【AtCoder】こんにちは！サトシ（@satoshi365_blog）です！ この記事では、「競技プログラミング（AtCoder）に登録し...

１０問目「Traveling」で身につくスキル

この問題では、こんなスキルが身につきます。

先に、これがどのようなスキルなのかを説明します。

 

「_」の使い方

「_」（アンダースコア）は、ゴミ箱のように使うことができます。

 

例えば、「”Hello”と10回表示したい」というときは下のように書きます。

for i in range(10):
  print('Hello')

 

でも、この「i」って変数、結局使わないですよね？

こういうときに、「_」を使います。

for _ in range(10):
  print('Hello')

 

このように「_」を使うと、下の2つのメリットがあります。

• メモリを余計に使わないで済む
• 使わない変数であることが一目でわかる

 

１０問目「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 ≤ 10⁵
・1 ≤ x_i ≤ 10⁵
・1 ≤ y_i ≤ 10⁵
・1 ≤ t_i ≤ 10⁵
・t_i ≤ t_i+1 ( 1 ≤ i ≤ N – 1 )
・入力は全て整数

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

N
t₁ x₁ y₁
t₂ x₂ y₂
.
.
t_N x_N y_N

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

ABC086C – Travelingより引用

 

入力例と出力例

入力例

出力例

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」の１０問を解くことができました！

この１０問で身につけたスキルを使って、どんどん問題を解いていきましょう！

 

他の問題の解き方も知りたい方は下の記事をお読みください。

サトシの競技プログラミング日記

 

もし分からない点などありましたら、気軽にTwitterやコメントなどでご質問ください＾＾

少しでも参考になれば嬉しいです！