はまやんはまやんはまやん

hamayanhamayan's blog

ThREE [Social Infrastructure Information Systems Division, Hitachi Programming Contest 2020 C]

https://atcoder.jp/contests/hitachi2020/tasks/hitachi2020_c

解説

https://atcoder.jp/contests/hitachi2020/submissions/10691704

条件が少し複雑なので、整理をする。
数が1,2,3,4,...とあるが、和か積が3の倍数というのは、結構満たしそうな感じがする。
3の倍数ということで、条件としては数はmod3で考えればよい。
1,2,3,1,2,3,1,2,3,...というのがあったときに和か積が3の倍数にならないのは、1と1, 2と2の組み合わせだけになる。
つまり、距離が3であって、1と1、2と2があるとだめ。
0,1,2の個数は大体N/3となる。

距離が3であってというのは、少し扱いにくい条件である。
ここで二部グラフを導入する。
木を二部グラフで分けたときに、1が2グループで分かれてしまうと、距離が3になる恐れがある。
二部グラフの性質を見れば、同じグループに入れておけば、距離が奇数にならないことは自明。
よって、1と2はそれぞれ全部同じグループに入れておくように配置できれば、それが答えになる。

二部グラフでサイズAとサイズBに分けることができたとする(A≦B)
Aが2の個数以上であれば、そこに2を全部入れて、もう片方に1を全部入れて、残りに3を入れていけばいい。
Aが2の個数未満であれば、そこに3を全部入れて、もう片方に1と2を全部入れる。
これで適切に構築が可能。

int N;
vector<int> E[201010];
int ans[201010];
//---------------------------------------------------------------------------------------------------
vector<int> grp[2];
void dfs(int cu, int pa = -1, int col = 0) {
    grp[col].push_back(cu);
    fore(to, E[cu]) if (to != pa) dfs(to, cu, 1 - col);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N - 1) {
        int a, b; cin >> a >> b;
        a--; b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }
    dfs(0);

    int A = grp[0].size();
    int B = grp[1].size();

    int one = N / 3; if (1 <= N % 3) one++;
    int two = N / 3; if (2 <= N % 3) two++;
    int thr = N / 3;

    if (A > B) {
        swap(A, B);
        swap(grp[0], grp[1]);
    } // A <= B

    if (two <= A) {
        // grp[0]を全部2にして、残りは3
        int x = 2;
        rep(i, 0, two) ans[grp[0][i]] = x, x += 3;
        x = 1;
        rep(i, 0, one) ans[grp[1][i]] = x, x += 3;
        x = 3;
        rep(i, two, A) ans[grp[0][i]] = x, x += 3;
        rep(i, one, B) ans[grp[1][i]] = x, x += 3;
    }
    else {
        // grp[0]を全部3にする
        int x = 3;
        rep(i, 0, A) ans[grp[0][i]] = x, x += 3, thr--;
        rep(i, 0, thr) ans[grp[1][i]] = x, x += 3;
        x = 1;
        rep(i, 0, one) ans[grp[1][thr + i]] = x, x += 3;
        x = 2;
        rep(i, 0, two) ans[grp[1][thr + one + i]] = x, x += 3;
    }

    rep(i, 0, N) {
        if (i) printf(" ");
        printf("%d", ans[i]);
    }
    printf("\n");
}