ABC126 D - Even Relation
2020-03-29
最近のコンテスト成績があまりにも酷いのでちょっとその対策というか施策として、てきとうに練習で解いた問題の考察と解法メモを書いてみる。
問題
解法
任意の頂点を一つ根として選択して何色でも良いので色を塗り、親との距離が奇数の子には親の色と違う色を塗る、ということをしながら DFS をした。
解説とはちょっと違う方法だった。
考察
まず木を作る。制約をみると、隣接行列だと とかになってデカくなりすぎてアレだと直感的に感じたので隣接リストで木を構築した。
次に色の塗分けについて考えたこと。
1: 大前提として偶奇の足し算は以下のようになる。
- 偶数 + 偶数 = 偶数
- 奇数 + 奇数 = 偶数
- 偶数 + 奇数 = 奇数
2: 奇数の辺で繋がっている頂点同士は自明に別の色にする必要がある。
上記 1 と 2 から、同じ色の頂点を結ぶ経路の辺は
- 偶数個の奇数辺 + 任意の数の偶数辺
になっていることがわかる。
ということは偶数の辺はどうでもよくて、奇数の辺についてだけ考えればよい。
そして色は2色なので、2回（というか偶数回）色を切り替えると同じ色になる。
よって、単純に奇数辺で結ばれる子を親と別の色で塗れば良さそうだとわかる。（例えば奇数辺が2回登場すれば同じ色になる。）
あとはそれをDFSで実装してAC。
感想
解説なしでACしたけど2回WAをだしてちょっと悩んだ。
WAの原因: 隣接リストを作るときに一方向にしか辺を張ってなかった。
ありがちなミスだと思うので気を付けたい。
以上。オワリ😇
