Livedoorブログからの移動
はてなブログからの移動

arc078.contest.atcoder.jp

解き方

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

ハマったところ

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

github.com