ARC078 D: Fennec VS. Snuke

arc078.contest.atcoder.jp

解き方

• 1から｀N`へのパス上をまず塗り、その後残りを塗るのが最適解
• 1とNからの距離でそのマスが黒か白か決まる
  • 1とNの2箇所から幅優先探索して、黒白それぞれの塗られる数を探索

ハマったところ

• Nヶ所から幅優先探索する方法を思い浮かばなかった
• パス(サイズO(n))を保存するDFS、BFSはO(N^2)

github.com