roiti46's blog

主に競プロ問題の解説を載せてます

Atcoder Beginner Contest #014

ABC過去問解きその2。A, B, C はサクッと解けたけど、木構造のノード間距離を効率的に求める必要のあるDは解説スライドと正解者のコードを参照しました。グラフとか木についての知識と経験が足りなすぎる。問題はこちら

A: けんしょう先生のお菓子配り

整数 a, b が与えられるので a に最低いくら足せば b で割り切れるかを答える問題。答えが0の場合もある。

a,b = int(raw_input()),int(raw_input())
print (b-a%b)%b

B: 価格の合計

2つの整数 n, X とn個の商品の価格が与えられる。Xを2進数表現した時の下から i 番目のビットが1なら i 番目の商品を合計価格に加えるとき、最終的な合計価格を答える問題。Xを1とアンド演算をして2で割っていけば、2進数表現で i 番目のビットが1かどうかを確認することができる。

n,X = map(int,raw_input().split())
a = map(int,raw_input().split())
ans = 0
for bit in range(n):
    if X&1: ans += a[bit]
    X /= 2
print ans

C: AtCoder

0から1,000,001の範囲の a <= b な a, b を n (最大1,000,001)個与えられる。各区間に含まれる範囲に+1の処理をしていったとき、全範囲での最大の値を答える問題。

各 a, b について a <= b の範囲の値を +1 ずつしていくとTLEになってしまう。この問題はいもす法を使えばO(n)で答えを計算することができる。具体的には hist[a] に1を足し、hist[b+1] に-1を足していく。すべての a, b について上記の処理が終わったら左から順に1つ前の要素を足しあわせていく。そうすれば与えられた区間についての+1の処理をまとめてすることができる。いもす法についてはいもすさんのサイトに詳しく書いています。

L = 1000002
hist = [0]*L
n = int(raw_input())
for roop in range(n):
    a,b = map(int,raw_input().split())
    hist[a] += 1
    hist[b+1] -= 1
for i in range(1,L):
    hist[i] += hist[i-1]
print max(hist)

D: 閉路

N 個のノードとあるノード間を結ぶ N-1 本の無向辺を与えられる。自己辺、多重辺は持たないとする。このときこのグラフは木構造となっていて、閉路が存在しないことが知られている。ノード ai と bi に新たに辺を加えると1つ閉路ができるのだが、この閉路の長さがいくつになるかを答える問題。N は最大で100,000である。加える辺についてのクエリ数 Q も最大100,000である。

各ノード間の距離を効率的に知りたい。そうすれば与えられた ai, bi に対して、 d(ai, bi) + 1 で答えとなる。グラフの各ノード間距離を求めるワーシャル・フロイド法で全点間距離をもとめるとO(N3)となりTLEとなってしまう。与えられたグラフは木構造をとっているのでそれをうまく利用する。

LCA(最小共通祖先)を用いてノード間距離を求めると満点解答ができる。具体的な手順は解説スライドやコードを見て欲しいのだが、2つのノード ai, bi の共通祖先で最も近いものの深さを効率的に求めることにより、2ノード間の距離を計算している。このコードを書くのに勝手ながらmitsuchieさんのコードを参考に(というかほぼ写経で)使わせていただきました。ありがとうございます。

#include <iostream>
#include <vector>
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define REP(i,a) FOR(i,0,a)
using namespace std;

const int MAXN = 1000001;
const int MAXM = 20; //2**20 = 1048576 > MAXN = 1000001

int N,Q,x,y,a,b;
int fs[MAXM][MAXN]; // fs[i][j]はノードjの2**i上のparentを格納する
vector<int> d(MAXN,-2); //各ノードの深さを格納。-2で初期化し未格納を表す。
vector<int> G[MAXN];  //ノードの連結を格納

// ノードのdepthと1つ上のparentについてdとfsに格納する。
void dfs(int index, int parent, int depth){
    d[index] = depth;
    fs[0][index] = parent;

    REP(i,G[index].size())
        if (d[G[index][i]] == -2)
            dfs(G[index][i],index,depth+1);
}

// 2ノードの共通祖先のうち最も近いもののノード番号を返す。
int lca(int aa, int bb){
    int a = aa; int b = bb;
    // 2ノードの深さを合わせる
    if (d[a] != d[b]){
        bool ab = d[a]<d[b];
        int len = ab ? d[b]-d[a]:d[a]-d[b];
        int c = ab? b:a;
        // fsのparent情報を利用して、効率的に根方向にたどっていく。
        REP(i,MAXM) if ((len>>i)&1) c = fs[i][c];
        a = ab ? a:c;
        b = ab ? c:b;
    }

    if (a == b) return a;
    
    // 2ノードが衝突する直前まで根の方向にたどる。
    // i = MAXM-1から調べることで処理が早くなる。
    for (int i = MAXM-2; i > -1; i--)
        if (fs[i][a] != fs[i][b]){
            a = fs[i][a];
            b = fs[i][b];
        }
        
    return fs[0][a];
}

int main(void){
    cin >> N;
    REP(i,N-1){
        cin >> x >> y;
        x--;y--;
        // 各ノード間のつながりを格納していく
        G[x].push_back(y);
        G[y].push_back(x);
    } 
    
    // ノード0を根として、各ノードのdepthと1つ上のparentを求める
    dfs(0,-1,0);

    // 各ノードの2**(i+1)上のparentのノード番号を格納していく。
    // fs[i][fs[i][j]] はノードjの2**i上のparentのさらに2**i上のparent
    // つまり2**(i+1)上のparentを指す。根より上の場合は-1。
    REP(i,MAXM-1)
        REP(j,N)
            fs[i+1][j] = (fs[i][j] == -1 ? -1:fs[i][fs[i][j]]);
            
    cin >> Q;
    REP(i,Q){
        cin >> a >> b;
        a--; b--;
        cout << d[a]+d[b]-2*d[lca(a,b)]+1 << endl;
    }
    return 0;
}
広告を非表示にする