perogram

B - Balanced Neighbors

Quiz

https://atcoder.jp/contests/agc032/tasks/agc032_b

Submit

https://atcoder.jp/contests/agc032/submissions/4705411

発想

f:id:peroon:20190325062233j:plain

  • 最初は上の図のように「どう線を引くか?」考えた
  • しかしSが不明なので手がかりがない
  • 下の図のように一度すべての辺を張ってから辺を削ったほうがイメージしやすい
    • 絶対音感と相対音感のようだ
  • 今回の場合、ピンクの線を切ればいい

実験

  • N=5, N=6でも実験すると、「取り除くべき辺のパターン」が見えてくる

f:id:peroon:20190325063025j:plain

解法

  • すべての辺を張ろうとする(出力しようとする)が、その前に「取り除くべき辺のパターン」かチェックして、その場合のみ張らない

学び

  • 今回の「1度全部辺を張ってから、条件を満たすように辺を切っていく」というのは余事象の考えに近い
  • そうやって見ると、見通しが良くなった