競技プログラミング

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

プログラミング

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

 

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

AtCoder で問題を解くためには、新規登録しないといけません。

新規登録はこちらから → AtCoder に新規登録する

 

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

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

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’ を出力してください。

ABC086C – Travelingより引用

 

入力例と出力例

入力例

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やコメントなどでご質問ください^^

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

COMMENT

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