2021-04-25 競プロチャレンジ供養会場: AtCoder Beginner Contest 199 (Sponsored by Panasonic) D - RGB Coloring 2 競技プログラミング AtCoder コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1804 (記事作成時点) 供養 解法 連結成分が異なる場合独立して計算できるので、以降は同一連結成分内で考えるものとする 頂点番号が小さい順に、各頂点が利用できる色の中から順に決めて探索する 「自身と隣接していて、自身より番号の小さい頂点の色」が利用できない色なので、その補集合をとる 利用できない色の集合を作るのは辺の数に依存 利用できる色は最初に選ぶ頂点を除き高々2種類 部分グラフに $K_{4}$ を含む場合は条件を満たす塗り方が存在しないが、その判定の有無はそこまで影響しない 実装 計算量は $O(M2^{N})$ 公式解説 躓いた点 実装が間に合わなかった
