Atcoder Beginner Contest #014
ABC過去問解きその２。A, B, C はサクッと解けたけど、木構造のノード間距離を効率的に求める必要のあるDは解説スライドと正解者のコードを参照しました。グラフとか木についての知識と経験が足りなすぎる。問題はこちら。
A: けんしょう先生のお菓子配り
整数 a, b が与えられるので a に最低いくら足せば b で割り切れるかを答える問題。答えが０の場合もある。
a,b = int(raw_input()),int(raw_input()) print (b-a%b)%b
B: 価格の合計
２つの整数 n, X とn個の商品の価格が与えられる。Xを２進数表現した時の下から i 番目のビットが１なら i 番目の商品を合計価格に加えるとき、最終的な合計価格を答える問題。Xを1とアンド演算をして２で割っていけば、２進数表現で i 番目のビットが１かどうかを確認することができる。
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)個与えられる。各区間に含まれる範囲に＋１の処理をしていったとき、全範囲での最大の値を答える問題。
各 a, b について a <= b の範囲の値を +1 ずつしていくとTLEになってしまう。この問題はいもす法を使えばO(n)で答えを計算することができる。具体的には hist[a] に1を足し、hist[b+1] に-1を足していく。すべての a, b について上記の処理が終わったら左から順に１つ前の要素を足しあわせていく。そうすれば与えられた区間についての+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 に新たに辺を加えると１つ閉路ができるのだが、この閉路の長さがいくつになるかを答える問題。N は最大で100,000である。加える辺についてのクエリ数 Q も最大100,000である。
各ノード間の距離を効率的に知りたい。そうすれば与えられた ai, bi に対して、 d(ai, bi) + 1 で答えとなる。グラフの各ノード間距離を求めるワーシャル・フロイド法で全点間距離をもとめるとO(N3)となりTLEとなってしまう。与えられたグラフは木構造をとっているのでそれをうまく利用する。
LCA(最小共通祖先）を用いてノード間距離を求めると満点解答ができる。具体的な手順は解説スライドやコードを見て欲しいのだが、２つのノード ai, bi の共通祖先で最も近いものの深さを効率的に求めることにより、２ノード間の距離を計算している。このコードを書くのに勝手ながら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と１つ上の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); } // ２ノードの共通祖先のうち最も近いもののノード番号を返す。 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); // 各ノードの２**(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; }
