AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019：C - Alternating Path(300)

問題

https://atcoder.jp/contests/aising2019/tasks/aising2019_c

考え方

コンテスト中に考えていたこと

グリッドグラフの問題。ぱっとみ二部グラフにしたくなる。過去の企業コンでも似たような問題があった。

各黒い点から dfs して白→黒→白→...とたどったときに白いマスがいくつあるか分かると嬉しい。うーんでもローカルで 400 × 400 のグリッドを投げるとスタックオーバーフローするな...どうしよう。

少し時間が立った後、まぁとりあえずsubmitしてみるかと思いsubmitした。 RE にならなかったけど TLE だった。(これはローカルのスタック領域が小さすぎたためだった...)。各黒いマスから dfs するのでは間に合わない。少し考えて見るとグリッドグラフ上で黒 - 白のマスを連結させたときに同じ集合に属する黒いマスから得られる白いマスの数は同じである。 →これは DisjointSet で頂点集合を管理しておけば良い。

あとは dfs するときに DisjointSet でメモ化して探索すればよい。

Submission #3994596 - AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019

どこに着目して考察するべきだったか

黒いマスと白いマスで連結したときに同一集合になる黒いマスをまとめることで計算量を落とすことができる。

何がバグっていたか

  • 配列の確保 int[H][W] の計算量は O(H \times W) であることを忘れていて O(H^2 \times W^2) になってしまって TLE していた。。。

  • ローカルのスタック領域が小さすぎた。(AtCoderと同じように -Xss256m とした)

  • 頂点の番号をかえす関数の実装がバグっていた

f(int i, int j) {
    return i * w + j
}

でよいのに、関数の引数を h w でとったいたために

f(int h, int w) {
    return h * w + w
}

でグローバル変数の w の値が取れていなかった...

得た知見

unionFInd木に色の情報をもたせると楽に実装できそうなので学習する。

類題