Official

A - Edge Checker 2 Editorial by kyopro_friends


AtCoder をはじめたばかりで何をしたらよいか分からない方は、まずは practice contest の問題A「Welcome to AtCoder」を解いてみてください。基本的な入出力の方法が載っています。
また、プログラミングコンテストの問題に慣れていない方は、AtCoder Beginners Selection の問題をいくつか解いてみることをおすすめします。


埋め込み

線で直接結ばれている点の組は \(14\) 組しかありません。したがって、入力がその \(14\) 組のいずれかであるかを調べればよいです。

実装例1 (Python)

a,b=map(int,input().split())
if (a,b)==(1,2) or (a,b)==(1,3) or\
    (a,b)==(2,4) or (a,b)==(2,5) or\
    (a,b)==(3,6) or (a,b)==(3,7) or\
    (a,b)==(4,8) or (a,b)==(4,9) or\
    (a,b)==(5,10) or (a,b)==(5,11) or\
    (a,b)==(6,12) or (a,b)==(6,13) or\
    (a,b)==(7,14) or (a,b)==(7,15):
  print("Yes")
else:
  print("No")

実装例2 (Python)

a,b=map(int,input().split())
if (a,b) in [(1,2),(1,3),(2,4),(2,5),(3,6),(3,7),\
            (4,8),(4,9),(5,10),(5,11),(6,12),(6,13),(7,14),(7,15)]:
  print("Yes")
else:
  print("No")

よりシンプルな解法

上で述べたような解法では、列挙漏れやタイプミスなどによって思わぬバグが混入することがあるため、可能であればよりシンプルな解法を探すべきです。
実は、今回の問題において答えが Yes となることは、\(a=\left\lfloor\frac{b}{2}\right\rfloor\) であることと同値になります(\(\lfloor \cdot \rfloor\) は切り捨てを表す)。したがって、次のようなシンプルな if 文で判定することができます。

a,b=map(int,input().split())
if a==b//2:
  print("Yes")
else:
  print("No")

おまけ

この問題のように、点同士の繋がり方に注目した構造をグラフといいます。グラフのうち、点同士が今回のように繋がったものは完全二分木と呼ばれます。完全二分木の点に今回のように番号付けをしたものは競技プログラミングにおいて頻繁に登場します。より難しい問題に挑戦するためには、今回登場した性質のことを覚えておくと良いでしょう。

posted:
last update: