The 46th World Championship ICPC P問題：Turning Red

問題. Turning Red

個のライトと 個のボタンがある。ライトは赤、緑、青の三色のいずれかで点灯する。ライトの色を変えることができるボタンを1回押すと、赤は緑に、緑は青に、青は赤に色を変える。
各ボタンに対して、そのボタンを押すと同時に色が変わるライトのリストが与えられる。ただし、各ライトに対して、そのライトの色を変えることができるボタンの数は高々 2 個である。また、あるライトの色を変えるボタンが与えられない場合もある。

初めに各ライトの色が与えられる。すべてのライトの色が赤色になるようなボタンの押し方で、押したボタンの回数の総和の最小値を答えよ。ただし、そのような押し方が無い場合は "impossible" と答えよ。

制約： 、

解法.

まず、赤、緑、青をそれぞれ 0, 1, 2 とおく。ライトの初期色を 、そのライトの色を変更できる 2 個のボタンを押した回数をそれぞれ とおいたとき、そのライトが赤色となるための必要十分条件は、

　　　

である。ただし、ボタンが 1 個の場合は、 であり、ボタンが 0 個の場合は、 である。答えはこのような合同式を満たすので、押したボタンの回数の総和の最小値という観点からは、各ボタンは多くても 2 回までしか押されない。

次に、色を変えることができないライトについて考える。そのようなライトで初期色が赤ではないものが一つでもあれば答えは存在しないので "impossible" を出力する。

それ以外の場合を考える。すなわち、各ライトの色を変更できるボタンが 1 個または 2 個ある場合である。よいボタンの押し方を見つけるために、次のような無向グラフ を考える。

・頂点集合：
・辺集合　：

実装では、辺集合 は多重辺を含んでいるが気を付ければ特に問題ないので、以降は単純グラフとして説明をする。
の任意の頂点 を考える。 に対応するボタンの押す回数を決めると、 を含む連結成分内のすべてのボタンの押す回数が決まる。なぜならば、 に隣接する頂点 は定義から、 と によって変更されるライトが少なくとも一つ存在する。そのようなライトを 1 つ適当に選ぶと、上の合同式を満たすために の押す回数が一意に定まる。このように の連結成分内のすべてのボタンの押す回数が決まったら、そによって変更されるすべてのライトが上の合同式を満たすか確認する必要がある。
あとは、 の押す回数を 0, 1, 2 の三通り試して、矛盾のないものの中で押したボタンの回数の総和が最小のものを選ぶ。各連結成分は互いに上の選び方によって独立しているので、各連結成分の求めた最小値の総和が答えとなる。ただし、3 通りの方法ですべて矛盾が出た連結成分が少なくとも一つある場合は解は存在しないので "impossible" と答える。

連結成分内で押した回数を伝搬させる方法は幅優先探索で実装した。実装上の注意として、上の を選び幅優先探索をするときに上手くデータを持たないと 時間かかる。例えば、連結成分毎に std::vector<int> visited(n) などと定義するだけでも TLE となるので注意（∵ すべての連結成分のサイズが 1 の場合）。

計算時間：

ソースコードを表示

#include <iostream>
#include <vector>
#include <optional>
#include <limits>
#include <queue>
#include <cassert>

std::optional<int> solve() {
    /** Input **/
    int n; // #lights
    int m; // #buttons
    std::cin >> n >> m;

    // ライトの初期色
    std::vector<int> initial_color(n);
    {
        std::string s;
        std::cin >> s;
        for (size_t i = 0; i < s.size(); ++i) {
            initial_color[i] = (s[i] == 'R' ? 0 : (s[i] == 'G' ? 1 : 2));
        }
    }

    std::vector<std::vector<int>> b(m); // b[i]：i 番目のボタンが変更するライトの列
    std::vector<std::vector<int>> l(n); // l[i]: i 番目のライトを変更するボタンの列
    for (int i = 0; i < m; ++i) {
        int num_lights;
        std::cin >> num_lights;
        b[i].reserve(num_lights);

        for (int j = 0; j < num_lights; ++j) {
            int light_id;
            std::cin >> light_id;
            --light_id;
            b[i].push_back(light_id);
            l[light_id].push_back(i);
        }
    }

    // 隣接グラフを構築
    std::vector<std::vector<std::pair<int, int>>> g(m);
    for (int i = 0; i < n; ++i) {
        if (l[i].size() == 0 && initial_color[i] != 0) {
            return std::nullopt;
        }
        else if (l[i].size() == 2) {
            // i 番目のライトを赤色にするために押すボタン回数を追加
            g[l[i][0]].emplace_back(l[i][1], (3 - initial_color[i]) % 3);
            g[l[i][1]].emplace_back(l[i][0], (3 - initial_color[i]) % 3);

        }
    }

    int min_button_press = 0;
    std::vector<int> num_press(m, -1);
    for (int s = 0; s < m; ++s) {
        // s を含む連結成分の押す回数は探索済み
        if (num_press[s] != -1) continue;

        // s 番目のボタンを num_press_s 回押す
        int local_min_button_press = std::numeric_limits<int>::max();
        for (int num_press_s = 0; num_press_s < 3; ++num_press_s) {
            std::queue<int> que1, que2;
            int sum_button_press = num_press_s;
            num_press[s] = num_press_s;
            que1.push(s);

            // s を始点とする幅優先探索（訪れた頂点を que2 に入れる）
            while (!que1.empty()) {
                const int v = que1.front();
                que1.pop();
                que2.push(v);

                for (const auto &e: g[v]) {
                    if (num_press[e.first] >= 0) continue;
                    num_press[e.first] = (e.second - num_press[v] + 3) % 3;
                    sum_button_press += num_press[e.first];
                    que1.push(e.first);
                }
            }

            assert(que1.empty());

            // 押し方に矛盾がないか判定
            bool can_turing_red = true;
            while (can_turing_red && !que2.empty()) {
                const int v = que2.front();
                que2.pop();
                que1.push(v);

                // v 番目のボタンのみ変更可能なライト
                for (int i : b[v]) {
                    if (l[i].size() == 1 && (initial_color[i] + num_press[v]) % 3 != 0) {
                        can_turing_red = false;
                        break;
                    }
                }

                // v 番目のボタンと他 1 個の計 2 個のボタンによって変更可能なライト
                if (can_turing_red) {
                    for (const auto &e: g[v]) {
                        if (0 != ((e.second - num_press[v] - num_press[e.first]) % 3)) {
                            can_turing_red = false;
                            break;
                        }
                    }
                }
            }

            // 矛盾しなければ s の連結成分のボタンを押す回数の総和の最小値を更新
            if (can_turing_red) {
                local_min_button_press = std::min(local_min_button_press, sum_button_press);
            }

            // 次の幅優先探索のために訪問済み頂点の履歴をリセット
            if (num_press_s < 2) {
                while (!que1.empty()) {
                    const int v = que1.front();
                    que1.pop();
                    num_press[v] = -1;
                }
                while (!que2.empty()) {
                    const int v = que2.front();
                    que2.pop();
                    num_press[v] = -1;
                }
            }
        }

        if (local_min_button_press == std::numeric_limits<int>::max()) {
            // s の連結成分はどのようにしても矛盾
            return std::nullopt;
        }
        else {
            // 答えに s の連結成分の値を追加
            min_button_press += local_min_button_press;
        }
    }

    return min_button_press;
}

int main() {
    auto min_button_press = solve();

    if (min_button_press.has_value()) {
        std::cout << *min_button_press << std::endl;
    }
    else {
        std::cout << "impossible" << std::endl;
    }

    return 0;
}

　

方針は立つけど実装で詰まる問題だった。大変。