1/15 PKU - Algorithmer’s note

2186 Popular Cows

N頭の牛がいて、「牛Aが牛Bを人気があると思う」というリストがある。AがBを人気があると思い、BがCを人気があると思うのなら、AがCを人気があると思うことになる。他のすべての牛に人気があると思われている牛の数を求めよ。

強連結成分分解するだけ

2201 Cartesian Tree

2つのキー(k, a)を持つ要素がいくつかある。これらの要素をノードに持ち、kに対しては二分探索木(左の子＜親＜右の子）、aに対してはヒープ（親＜子）になるような木を構築せよ。

kでソートして、ある範囲の木を構築するときはその中でaが最小になるものを見つけて、それより左と右について再帰的に解く。最小のものを見つけるのはSegment Treeを使う。

3134 Power Calculus

最初にxがあって、「今までにでてきた計算結果から2つ選んで、掛けるか割るかして新しく計算結果とする」ことができる。x^nを求めるには、最低何回計算する必要があるか。
例えば、x^31を求めるには、x -> x^2 -> x^4 -> x^8 -> x^16 -> x^32 -> x^31とすれば6回で求まる。

全探査に枝刈りを仕込む。

2331 Water pipe

パイプがいくつかある(4種類以下、それぞれ10本以下)。平面状のある点からある点まで、パイプをつなげて結びたい。パイプ同士がつながるとき、なす角は180度か90度でないといけない。最低何本のパイプが必要か。

X方向差分とY方向差分をとって、全探査で「あるパイプの選び方」でその差を達成できるか調べる。ここで、何個の直線が必要か覚えておく。それで、すべての取り方について、「その取り方でX方向が可能でかつ残ったパイプでY方向が可能か」調べる。直線の個数が2以上違うとなす角0度が発生するのでだめ。

3015 Expected Difference

N個の要素を持つ数列から、適当にM個を選ぶ。(最大値-最小値)の値の期待値を求めよ。

(最大値の期待値)-(最小値の期待値)を求める。数列のi番目(0-origin)の要素が最小値になる確率は、(_N-iP_M-_N-i-1P_M)/(_NP_M)に等しい。これを変形して、最小値の期待値は
v[0]*m/n + v[1]*m*(n-m)/n(n-1) + v[2]*m*(n-m)(n-m-1)/n(n-1)(n-2)…となる。
係数をdoubleで持って置いて、順次掛けたり割ったりして求める。入力の数列はソートされているので、O(N)