かしのブログ

競技プログラミングとか

日立製作所社会システム事業部プログラミングコンテスト2020 C - ThREE

AtCoder 二部グラフ

問題

与えられた $N$ 頂点の木の頂点1から頂点 $N$ に、次の条件を満たすように1から $N$ の順列 $p_i$ の番号をつける。

任意の頂点の組 $(i, j)$ で、頂点 $i$ と頂点 $j$ の距離が3なら、 $p_i +p_j$ か $p_i \times p_j$ が3の倍数になる。

考察

$q_i = p_i \% 3$ を表す。 $(q_i, q_j) = (0, n), (n, 0)$ なら、積が3の倍数になる。 $(q_i, q_j) = (1, 2), (2, 1), (0, 0)$ なら、和が3の倍数になる。それ以外のペア $(q_i, q_j) = (1, 1), (2, 2)$ で和や積が3の倍数になるペアは作れない。

与えられた木を二部グラフと捉えると、距離が3の2つの頂点はそれぞれ異なる頂点集合に属する。この異なる頂点集合から任意の頂点のペアを取り出したときに、 $(q_i, q_j) = (1, 1), (2, 2)$ とならないようにすればよい。具体的には、 $q_i = 1$ なる点はすべて同じ集合に、 $q_i = 2$ なる点もすべて同じ集合に、入れれば良い。

実装