Regionals 2011 :: Asia - Kanpur

Live Archive

Strongly Connected Chemicals

問題

(V=L∪R,E)な2部グラフGが与えられる。
L'⊂L,R'⊂R（|L'|>=1, |R'|>=1）なL',R'を選んで、
全ての(i,j)∈L'×R'の間に辺があるようにしたい。
このとき|L'|+|R'|の和の最大値を求めよ。

制約

1 ≤ m, n ≤ 50

解法

L'=ΦもしくはR'=Φも許す場合は2部クリークというらしい。
最大クリークは補グラフに対する最大独立集合と等価らしい。
2部グラフの最大独立集合は(頂点数-最大マッチング)となる。
これで2部クリークは解けるが、この問題は左の頂点と右の頂点をそれぞれ1つ以上選ばなければならない。
そこで、頂点a(∈L)と頂点b(∈R)（(a,b)∈E）は必ず選ぶことにして、
~L = {i∈L | (i,b)∈E}
~R = {j∈R | (a,j)∈E}
~G = 頂点~L∪~RなGの部分誘導グラフ
としたとき、~Gの最大2部クリーク+2の最大値が答えになる。

Confusion in the Problem Set

問題

a[0],a[1],...,a[n-1]が与えられる。
a[i]を並べ替えて、
a[i] ∈ {i, n-i-1}
を満たすようにしたい。
このような並べ替え方法があるか判定せよ。

制約

T<=60
n<=10^4
a[i]<=10^6

解法

b[i] = iまたはn-i-1の数 (i < (n+1)/2)
とする。
nが偶数のとき、b[i] > 2なるb[i]があったらno。
nが奇数のとき、b[i]>2,i1ならばno。
それ以外ならyes。

LCM Extreme

問題

[tex:\sum_{1<=i

制約

T <= 25000
n <= 5*10^6

解法

http://apps.topcoder.com/forums/?module=Thread&threadID=729936&start=0&mc=2#1473205
の通り実装したら通った。
S(n) = n*(1+S2(n))/2
を計算するときに2で割るのに躊躇したが、
少なくともnや1+S2(n)はunsigned long longの範囲を超えないので大丈夫だった。

Tetromino

10^6*log(N)くらいに出来るのかなあ・・・

Blade and Sword

ただのBFS

The Falling Circle

問題

円c1,円c2,円cが与えられる。
c1とc2の接線のうち、接点のy座標が中心のy座標より小さいものが地面となる。
円cはこの地面より上にあり、秒速1で落ちる。
地面まで落ちたら地面が傾いている方に転がり、c1もしくはc2にぶつかったら止まる。
ここで、c1とc2の間に落ちることは保証される。
cは1秒で1回転する。
このとき、cが落ち始めてから止まるまでにかかる時間を求めよ。
ただし地面が傾いていなければ落ちた所で止まる。

制約

T<=10000

座標 <=10^5

1<=半径<=100

解法

接線は上手いこと下側のもの１つを取ってくるようにする。
接線を表すときに(c1における接点),(c2における接点)を保持しておくと良い。
地面と落ちたとき円cの中心がどこになるかは二分探索で求めた。
転がる距離は点と直線の距離と三平方の定理を用いることで求まる。

My Visit to Spring Secret

超やるだけ

Scrabble

無かった

An Average Game

問題

数列a[1],..a[n]がある。
クエリがQ個来るので、各クエリに対して
a[li],...,a[ri]をセットに入れたときの値の平均を求めよ。

制約

T<=100
n<=10^4

a[i] <=10^9

Q<=10^5

解法

数列aを平方分割する。
またa[i]を座標圧縮して0~hogeの値として考え、要素数10000テーブルに入れられるようにする。
座標圧縮後のa[i]に対応する値をb[i]とする。
前処理として、

をO(n√n)で求めておく。

クエリに対しては、
liに対応するバケットをlid, riに対応するバケットをridとすると、
p[rid][b[i]] - p[lid+1][b[i]] == 0
であるとき、間に挟まれたバケットに関してb[i]は現れてないことが分かる。
この事実と、SUM、NUMを使うことで、
liからriまでのdistinctな値の和と数を求めて平均を算出する。
これはO(√n)で行うことが出来る。

よって計算量O(n√n + Q√n)
で解ける。

Permutation Counting

問題

1~nの順列で、a,a+1がこの順で隣接しているような部分がないものの数を求めよ。

制約

T <= 10000
1 ≤ N ≤ 10^6

解法

http://oeis.org/A000255
OEIS無しだとどう考えたら解けるんだろう