D - 閉路

時間制限 : 2sec / メモリ制限 : 256MB

問題文

n 個の頂点と n−1 本の辺からなる連結な無向グラフが与えられます．それぞれの頂点には 1 から n までの番号が順番にふられています．

グラフ理論において，このような条件を満たすグラフは木と呼ばれ，閉路を含まないという性質があります．このグラフに対し，元のグラフに含まれない追加辺 (a,b) を1つ追加したグラフについて考えてみると，このグラフはちょうど1つの閉路を含みます．あなたの仕事は，そのようなグラフについて，閉路の長さ(閉路に含まれる辺の数)を出力することです．ただ，追加辺の候補はいくつかあり，Q 個与えられるので，それら全ての候補について答えを出力してください

Note

多くの知見が得られた良問 lca(lowest common ancestor)をただ求めるだけでなく2^n先の親を保持することで２分木探索が可能になる。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX_N 100001
#define MAX_LOG_N 18

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

using namespace std;

struct Edge
{
    int a, b;
};

struct Node
{
    int val, depth, parent;

};

void bfs(int start, vector<int> G[], int size, vector<vector<int> >& p, vector<int> &d){
    queue<Node> q;
    vector<int> check(size, 1); //　未訪問は1
    Node n = {start, 0, -1};
    p[0][start] = -1;
    d[start] = 0;
    check[start] = 0;
    q.push(n);
    while(!q.empty()){
        Node cur = q.front();
        q.pop();
        for (int i = 0; i < G[cur.val].size(); ++i)
        {
            int next = G[cur.val][i];
            if(check[next]){
                check[next] = 0;
                Node tmp = {next, cur.depth + 1, cur.val};
                p[0][tmp.val] = tmp.parent;
                d[tmp.val] = tmp.depth;
                q.push(tmp);
            }
        }
    }
}

void init_p(vector<vector<int> >& p, int size){
    for (int i = 0; i < MAX_LOG_N - 1; ++i)
    {
        for (int j = 0; j < size; ++j)
        {
            if(p[i][j] == -1){
                p[i+1][j] = -1;
                continue;
            }
            p[i+1][j] = p[i][ p[i][j] ];
        }
    }
}

int lca(int a, int b, const vector<vector<int> >& p, int size, const vector<int> &d){
    if(d[a] > d[b]) swap(a, b);
    int diff = d[b] - d[a];
    for (int i = 0; i < MAX_LOG_N - 1 ; ++i)
    {
        if(diff >> i & 1){
            b = p[i][b];
        }
    }
    if(a == b) return a;

    for (int i = MAX_LOG_N - 1; i >= 0; --i)
    {
        if(p[i][a] != p[i][b]){
            a = p[i][a];
            b = p[i][b];
        }
    }
    return p[0][a];
}

int main(){
    int n, q;
    vector<int> G[MAX_N];
    cin >> n;
    for (int i = 0; i < n-1; ++i)
    {
        int x, y;
        cin >> x >> y;
        x--; y--;
        G[x].push_back(y);
        G[y].push_back(x); 
    }

    cin >> q;
    vector<Edge> edges;
    for (int i = 0; i < q; ++i)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        Edge e = {a, b};
        edges.push_back(e);
    }

    vector< vector<int> > p(MAX_LOG_N, vector<int>(n, -1)); 
    vector<int> d(n, -1);
    bfs(0, G, n, p, d);
    init_p(p, n);

    for (int i = 0; i < edges.size(); ++i)
    {
        cout << d[edges[i].a] + d[edges[i].b] - d[lca(edges[i].a, edges[i].b, p, n, d) ]*2 + 1 << endl;
    }

}

C - AtColor

時間制限 : 3sec / メモリ制限 : 256MB

問題文

　AtColor社は，0 から 1,000,000 まで 1,000,001 通りの濃さがある灰色の絵の具を販売することにしました．0 が最も黒く，1,000,000 が最も白い絵の具です．

　しかし，途方も無い数の濃さのバリエーションがある一方，消費者には細かい違いが分からないということが判明しました．これを知ったAtColor社は，売れない濃さの絵の具を生産するのはやめて，最も人気のある濃さの色の絵の具1つだけを販売することにしました．

　AtColor社は上記を達成するために，最も人気な絵の具がどのくらい売れるかをアンケート調査で調べることにしました． AtColor社がどの範囲の濃さの絵の具なら購入したいかというアンケートを消費者に対して行ったところ，「a≦x≦b を満たす濃さ x の絵の具ならば購入する」という形式の情報が n 件得られました．

　あなたの仕事は，これらの情報から，最も多くの消費者に購入される濃さの絵の具について，その絵の具を購入する消費者の数を出力するプログラムを作ることです．

note

いもす法使うだけansの初期値をimos[0]にするとこだけ注意

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX_N 1000001
#define ll long long
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

using namespace std;

int main(){
    int n;
    ll imos[MAX_N+1];
    Fill(imos, 0);
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        int a, b;
        cin >> a >> b;
        imos[a]++;
        imos[b+1]--;
    }

    ll ans = imos[0];
    for (int i = 1; i <= MAX_N; ++i)
    {
        imos[i] += imos[i-1];
        ans = max(ans, imos[i]); 
    }

    cout << ans << endl;

}

TakefumiYamamura / programming_contest

AtCoder Beginner Contest 014 #21

D - 閉路

問題文

Note

C - AtColor

問題文

note