2020-01-19

キーエンスプログラミングコンテスト 2020 E - Bichromization (黄色, 900 点)

AtCoder AtCoder900点構築探索順序を工夫して解く最大値や最小値に着目する木 Union-Find 必要条件を列挙したら十分条件になる Greedy:端から順に決まっていく Greedy 二部グラフパリティ黄色diff ARC-like second best を管理する

実装に精彩を欠いてしまった...コンテスト中に WA を取りきれず...

WA の原因は「すでに色を決めたはずの頂点について再度色を上書きしていることがある (現在見ている D 値について、それより小さい値の頂点とはつながっておらず、等しい D 値同士で結ばれた辺の両端をともに着色する場合)」というものだった。

問題へのリンク

問題概要

$N$ 頂点、 $M$ 辺からなる連結な無向単純グラフが与えられる。各頂点 $v$ には整数値 $D_{v}$ がついている。今、各頂点を白・黒に塗り分けて、各辺に 1 以上 10⁹ 以下の整数値の重みを割り振って、以下の条件を満たすようにしたい。

白く塗られた頂点が存在
黒く塗られた頂点が存在
どの頂点 $v$ についても、その頂点と色が異なるような頂点のうち、もっとも距離が近い頂点への最短路長が $D_{v}$ である

このようなことが可能かどうかを判定し、可能ならば具体的な解を一つ構成せよ。

制約

$2 \le N \le 10^{5}$
$1 \le M \le 2 \times 10^{5}$

考えたこと

最初は摑みどころがないので、どういう場合ができないのかを考えてみることにした。たとえば

N = 2
M = 1
E = {(1, 2)}
D = {1, 3}

とかはできない。頂点 1 と頂点 2 を別々の色に塗ることになるが、それらを結ぶ辺の値を 3 未満にはできない。なぜならそうすると、頂点 2 から頂点 1 への最短路が 3 未満であることになって、D[2] = 3 に矛盾するため。よって辺の値は 3 でなければならないが、今度は D[1] = 1 に矛盾してしまう。

というわけで、N = 2、M = 1 の場合は、D[0] と D[1] が等しくなければならない。一般に、辺 (u, v) の両端を別々の色で塗るとき、辺の値は max(u, v) 以上でなければならず、u と v のうちの D の値が小さい側については、他の頂点との最短路がその値になるようにする必要がある。

...ということを考えると、究極の「D の値が最小の頂点」に着目したくなる。

D の値が最小の頂点に着目する

まず、D の値が最小の頂点 v が、単独で存在したとする。このとき、絶対に無理。なぜなら、v と隣接するどの頂点 w についても、辺 (u, v) の値は、max(Du, Dv) (> Dv) 以上でなければならない。しかしそうすると、v についての条件を満たせない。

逆に、D の値の最小値を m としたとき、D_v = m となる v に隣接する頂点で存在して D の値が m である場合は、上手く行く。その辺に m を割り当てればよい。

整理すると、D の値が m (最小値) であるような頂点集合が以下の条件を満たす必要がある。

隣接関係がある部分についてグループ分けしたとき、孤立しているグループを含まない (グループがいくつかに分かれるのは OK)

次に、D が 2 番目に大きい頂点 v の集合について考察すると、今度は以下のことが必要であるといえる

頂点 v が、D の値が最小の頂点と隣接している
頂点 v が、D の値が同じ頂点と隣接している

いずれも、その隣接している頂点をどれか一つ選んで、その辺に値 D[v] を振れば OK。一般に、同様にして以下のことがいえる

任意の頂点 $v$ について、 $v$ に隣接する頂点のうち、ある頂点 $w$ が存在して、 $D_{w} \le D_{v}$ となることが必要である

そしてこれが十分でもあるのだ！！！証明は実はそんなに難しくない。

各頂点 $v$ に対して、 $D_{w} \le D_{v}$ が成立するよな頂点 $w$ を見つけ、辺 $(v, w)$ のみを取り出す

ということをしてできる部分グラフを考えると、その各連結成分は

サイクル
木

のいずれかになる。サイクルの場合は、それに含まれるすべての頂点の D 値が等しいことになる。よって、辺を上手く入れ替えれば木にできる。よって結局、各連結成分は木になる場合のみ考えればよい。木の場合は、その木に含まれる各辺 (u, v) について、その値を max(D[u], D[v]) とすれば OK。さらに木は二部グラフなので、どの辺の両端も色が異なるようにできる。そして、サイクルにも木にも属さない辺は悪さをしないようにすべて INF にしておく。

このように構成した解は条件を満たしている。

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
using pint = pair<int,int>;
using Graph = vector<vector<pint>>;
const int INF = 1000000000;

int N, M;
Graph G;
vector<int> D;

void solve() {
    map<int, vector<int>> ma;
    for (int v = 0; v < N; ++v) ma[D[v]].push_back(v);

    vector<int> color(N, -1);
    vector<int> res(M, INF);
    for (auto it : ma) {
        int val = it.first;
        auto vs = it.second;
        for (auto v : vs) {
            if (color[v] != -1) continue; // 既に処理済み
            bool exist = false;
            for (auto e : G[v]) {
                int nv = e.first;
                if (D[v] < D[nv]) continue;
                exist = true;
                res[e.second] = val;
                if (color[nv] == -1) {
                    color[v] = 0;
                    color[nv] = 1;
                }
                else color[v] = 1 - color[nv];
                break;
            }
            if (!exist) {
                cout << -1 << endl;
                return;
            }
        }
    }
    for (int i = 0; i < N; ++i) {
        if (color[i] == 0) cout << "W";
        else cout << "B";
    }
    cout << endl;
    for (int i = 0; i < M; ++i) cout << res[i] << endl;
}

int main() {
    cin >> N >> M;
    D.resize(N);
    for (int i = 0; i < N; ++i) cin >> D[i];
    G.assign(N, vector<pint>());
    for (int i = 0; i < M; ++i) {
        int u, v; cin >> u >> v; --u, --v;
        G[u].emplace_back(v, i);
        G[v].emplace_back(u, i);
    }
    solve();
}