ABC021-B - 嘘つきの高橋くんを解く

ABC021-B - 嘘つきの高橋くん

問題が何言っているのかよくわからない…

最短経路の可能性があるかどうかを求める問題らしいが…

とりあえず入力例を見てみよう

…

なるほど

入力例1とその説明を見てなんとなく問題の意味はわかった

町の数と、出発する町の番号、到着する町の番号、

経由した町の番号が与えられるので

それらで最短経路を構成できるなら "YES"を

できないなら "NO"を出力しろということらしい

入力例1は "YES" のパターンの説明だ

入力例2・3は "NO" のパターンの説明。どういうときに "NO" となるのか…？

入力例2

7
1 3 // 出発地点、到着地点
4
2 4 2 7 // 経由地点

入力例3

4
1 4 // 出発地点、到着地点
3
2 1 3 // 経由地点

なるほど、どうやら

経由地点の番号に重複があったり

出発地点や到着地点の番号が経由地点に含まれていると NG

のようだ

以上を踏まえてコードを書いてみよう

提出したコード

# 入力
N=int(input())
a,b=map(int,input().split())
K=int(input())
l=list(map(int,input().split()))

# 出発地点や到着地点が経由地点に含まれていたらNG
if a in l or b in l:
  print('NO')
  exit()

# 経由地点の重複を除去
setl=list(set(l))

# 経由地点に重複があったらNG
if len(setl)!=len(l):
  print('NO')
  exit()

# 上記のチェックにかからなければOK
print('YES')

考えて競プロする

プログラミングコンテストの問題をどう考えて解いたかを記録していくブログです。使用言語はPython3

ABC021-B - 嘘つきの高橋くんを解く