ARC030_A(閉路グラフ)

問題

• AtCoder Regular Contest 030 - A

考えたこと

• 問題の意味がわからなかったため解けなかった
• 連結成分 の意味を調べて理解できたので, きちんと備忘録として記録する
  • 連結成分 = 1つの独立したグラフ の こと
• 今回の問題の場合, ノードが1つしか無いグラフに分割していくのが最適
• 1個飛ばしでノードを切り離していくことになるので n / 2(切り捨て) が最大の連結成分数
• k が 最大の連携成分より小さければ作成可能, そうでなければ作成不可
• あとは実装のみ

実装

n = int(input())
k = int(input())

# n >= 3 なので 0になることはない
limit = n // 2

if k <= limit:
    print("YES")
else:
    print("NO")

結果

• 上記コードで無事に AC
• ABCは問題も丁寧だけど, ARCの問題とかだと数学(?)の用語をきちんと知らないと解けない