mini notes

競技プログラミングの解法メモを残していきます。

日立コン2020 C - ThREE (600)

問題:C - ThREE

解答:Submission #10717648 - Social Infrastructure Information Systems Division, Hitachi Programming Contest 2020

解法:piとpjの和または積が3の倍数であることは、「pi, pjが1 (mod 3), 2(mod 3)のそれぞれどちらか」または「pi, pjのどちらかが0 (mod 3)」であることである。よって、各頂点に対し、mod3で0, 1, 2を上記の条件を満たすように当てはめることを考える。

ここで頂点1を根とすると、距離が3だけ離れている2頂点については、根からの距離の偶奇が異なる。よって根からの距離が偶数のものと奇数のものに分け、各頂点にどの数を当てはめるとよいか考える。

根からの距離が偶数の頂点を偶数頂点と呼び、その個数をtcnt個とする。同様に根からの距離が奇数の頂点を奇数頂点と呼び、その個数をfcnt個とする。

tcnt > n/3 かつ fcnt > n/3の場合、例えば偶数頂点に1を、奇数頂点に2を当てはめてゆき、1・2が足りなくなった場合0を当てはめるという方法を考える。このとき、条件より1は偶数頂点で、2は奇数頂点で使い切れるためうまくいく。

tcnt ≦ n/3のとき、上記の方法を用いると、偶数頂点で1を使いきれない可能性がある。すると奇数頂点で1を使うことになり、偶数頂点と奇数頂点で1が両端となる辺が出てしまう可能性がある。よって上記の方法は使えない。ここで先に偶数頂点で0を使うこととすると、条件より偶数頂点はすべて0が割り当てられることになり、このとき奇数頂点は0, 1, 2どれでもよいことになる。

fcnt ≦ n/3のときも同様である。