競技プログラミングでも出題されそうな数学オリンピックの問題

この記事では、数学オリンピックで出題された問題を競技プログラミングの形式に変換して紹介します（変換とは言ったものの、制約以外一切改変なしです）。実行時間とメモリの制限は2秒、1024MB程度を想定しています。

問題

頂点 辺の連結な単純無向グラフが与えられます。頂点には の番号が、辺には の番号が振られており、辺 は頂点 と を結びます。数列 と であって、次の条件を満たすものを つ構築してください。

• は または
• は または または
• 頂点 に対して を 　で定める。 つの頂点 と が隣接するとき、である。

（出典：Baltic Way 2020 Problem 9　Baltic Way 2020 – virtual competition）

制約

• 
• 
• 
• 
• 与えられるグラフは連結な単純グラフである。

解説

クリックで解説を見る

と初期化します。からの順に、であるすべてのに対してとなるように調整していきます。

頂点についての調整は次のように行います。
頂点に隣接する頂点のうち、インデックスが未満であるものの個数を個とします。ならについての調整は終わりです。
頂点に隣接する頂点のうち、インデックスが未満であるものをつ選んでとします。とを結ぶ辺を辺とすれば、いまのの値は初期値のままです。したがって、

• いまならば、に変更する
• いまならば、に変更する

ことで、の値を変えることなくの値をだけ変更できます。
これが、個の頂点すべてについてできるので、以外の頂点のの値を変えることなく、の値を種類から自由に選べることになります。について禁止されている値（すなわち、の値）は高々種類なので、これらを踏まないようにの値を選べます。

調整の回数は回で、の総和はなので、このアルゴリズムを実装すれば間に合います。

クリックで実装例を見る（C++）

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> iint;

// output
template<class T> ostream& operator<<(ostream &ostr, const vector<T> &vec){
    int N = vec.size();
    if(N == 0) return ostr;
    ostr << vec[0];
    for (int i = 1; i < N; i++) {
        ostr << " " << vec[i];
    }
    return ostr;
}

int main(){
    int N, M;
    cin >> N >> M;
    vector<vector<int>> G(N);
    map<iint, int> mp;
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        if(u > v) swap(u, v);
        G[v].push_back(u); // indexの大きい頂点からのみ参照
        mp[{u, v}] = i; // 辺番号
    }

    vector<int> A(N, 1); // A_i
    vector<int> B(M, 2); // B_i
    vector<int> S(N, 1); // S_i
    for (int i = 0; i < N; i++) {
        for (int v : G[i]){
            S[i] += 2;
            S[v] += 2;
        }
    }

    for (int i = 0; i < N; i++) {
        int si = S[i];
        int mins = si; // S_i を区間[mins, maxs]の整数から選べる
        int maxs = si;
        int k = G[i].size();
        set<int> s;

        for (int j = 0; j < k; j++) {
            if(A[G[i][j]] == 1){
                mins--;
            }
            else{
                maxs++;
            }
            s.insert(S[G[i][j]]);
        }   

        int news; // S_i を newsに変更する
        for (int j = mins; j <= maxs; j++) {
            if(!s.count(j)){
                news = j;
                break;
            }
        }
        for (int j = 0; j < k; j++) {
            if(A[G[i][j]] == 1){
                if(news < S[i]){
                    A[G[i][j]] = 2;
                    B[mp[{G[i][j], i}]] = 1;
                    S[i]--;
                }
            }
            else{
                if(news > S[i]){
                    A[G[i][j]] = 1;
                    B[mp[{G[i][j], i}]] = 3;
                    S[i]++;
                }
            }
        }   
    }

    cout << A << endl;
    cout << B << endl;
}