Hatena::Grouptopcoder

capythm@TopCoder このページをアンテナに追加 RSSフィード

2015-01-12Codeforces #285 (Div.1)

Codeforces #285 (Div.1)

23:46 | Codeforces #285 (Div.1) - capythm@TopCoder を含むブックマーク はてなブックマーク - Codeforces #285 (Div.1) - capythm@TopCoder Codeforces #285 (Div.1) - capythm@TopCoder のブックマークコメント

A. Misha and Forest

問題

http://codeforces.com/contest/504/problem/A

無向グラフがある。頂点がN個(0, 1, ..., n-1)ある。ループや多重辺はない。

各頂点につながっている枝の数degree[k]と、つながっている先の頂点をxorした結果s[k]が与えられる。

グラフの全ての枝(V_from, V_to)を出力せよ

解法

ループがないので、葉があることが保証される。

degree[k]=1のものから処理していく。degree[k]=1の頂点は親ノードparent[k]=s[k]であることは自明。

親ノードの情報degree[ parent[k] ],s[ parent[k] ]も更新する(自ノードを切り離す)。

これを逐次実行すれば解ける。degree[k]=1になったものをqueueに突っ込んで順番に処理すると実装が楽。

ソースコード

http://codeforces.com/contest/504/submission/9415856

B. Misha and Permutations Summation

問題

http://codeforces.com/contest/504/problem/B

n個の数字(0, 1, ..., n-1)の順列はn!パターンある。これを順番にソートして、k番目の順列をPerm(k)と定義する。

つまり、Perm(0)=(0, 1, ..., n-1), Perm(n!-1)=(n-1, n-2, ..., 0) である。

2つの順列Perm(x), Perm(y)を与える。Perm((x+y) mod n!)を出力せよ。

解法

順列Perm(x)からxを求める必要がある。これには、階乗進数への変換が便利である。

例えば、3要素の階乗だと

s

012 -> 0 = 0*2! + 0*1!

021 -> 1 = 0*2! + 1*1!

102 -> 2 = 1*2! + 0*1!

120 -> 3 = 1*2! + 1*1!

201 -> 4 = 2*2! + 0*1!

210 -> 5 = 2*2! + 1*1!

という具合だ。

つまり、順列s[0..n-1]から A[1]*1! + A[2]*2! + ... + A[n-1]*(n-1)! の A[i]を求めたい。

上の例を見ると、A[2]はs[0]の値そのものであり、

A[1]はs[1]がs[1..2]の中で何番目に大きいか、の値になっている。

よく考えると、A[2]もs[0..2]の中で何番目に大きいか、の値だ。

A[n-1]は容易に求まるが、A[n-2]以降は容易ではない。

(n<=200,000なので、ナイーブな方法O(n^2)では計算が間に合わない)

そこで、BITを使う。B[0]=B[1]=...B[n-1]=1で初期化しておき、

A[n-i-1]=sum(B[0]... B[ s[i] ]) (=BIT.get(s[i]))で求め、B[ s[i] ]=0に更新(BIT.add(s[i],-1))するとよい。

BITを使うことで計算量がO(n log n)に減るので間に合う。

xからPerm(x)を生成する処理も必要だが、上記の逆をすればいい(多分)ので省略します。

具体的な実装は他の人のソースを見てください(´・ω・`)