Ural FU contest. Kontur Cup. Petrozavodsk training camp. Winter 2013

http://acm.timus.ru/contest.aspx?id=153
ロシアの怖い合宿で出題されたセットらしい。チームで解いたが10問あって2完という怖いセットだった。
本番ではC,Iを解いて後でA,Fを解いた。

A - Complex Root

問題

x^n = a+bi
x^m = c+di
を満たすような複素数xの個数を求めよ。

制約

<= 10^18

1 <= n,m <= 100
a^2+b^2 > 0
c^2+b^2 > 0

解法

x^n = a+bi　…　(i)
だけを考えると、
xの候補の１つは絶対値が|a+bi|^(1/n)、偏角がa+biの偏角を1/nしたものであり、
他はそれに1のn乗根をかけたもの（すなわちk/n回転したもの）の計n個解が存在する。
x^m = c+di　…　(ii)
も同様である。

(i)と(ii)を同時に満たすようなxの偏角θはa+biの偏角をθ1、c+diの偏角をθ2とすると
θ = θ1/n + 2πk/n = θ2/m + 2πk'/m (mod 2π)…　(iii)
となる。
よって、gcd(n,m)=g, lcm(n,m)=lとしたとき、
θ1/n = θ2/m (mod 2π/l)　…　(iv)
であれば、
θ = θ1/n + 2πk/g (k = 0, 1, ..., g-1)
は全てこの場合に限り(iii)を満たす。

ここで、(θ1/n)*l = (θ2/m)*l (mod 2π) ならば (iv)を満たす。
よって、(i)から求めたx^lと、(ii)から求めたx^lが等しければ、(i)と(ii)を同時に満たす
xがg個ある事がわかる。

以上より、(a+bi)^(m/g) = (c+di)^(n/g)を満たすかどうか多倍長で判定し、
満たすならg、満たさないなら0が答えとなる。

F - Fire Signals

問題

2次元座標上のn個の点が与えられる。
このとき直線を引いて、各点からその直線までの距離の和を求めるとき、
その最小を求めよ。

制約

2 <= n <= 1000

座標

<= 10^6

解法

証明はよく分からないが、答えを満たす直線は2点を通るような直線として良い。
1次元の場合だと1点を通るような直線（点）としてよいし、それと同じようなものだと直感的には感じる。
そこで、1点を固定して直線を回す。直線の上側（反時計回り方向）と下側（時計回り方向）にある点を分けて直線がx軸と重なるように回転すると、そのときの答えは
上側の点のy座標 - 下側の点のy座標
となる。
これをO(1)で計算するために、両側それぞれに対するx座標のsumとy座標のsumを保持しておく。
すると回転行列から回転後のy座標のsumが一発で求まる。
２点以上が同じ座標にある場合に注意。
O(n^2log n)

I - GOV-internship 3

問題

文字列sとパターン文字列pが与えられる。
アルファベットは0から100000の整数である。
ここで、アルファベット0は1から100000のいずれにも変える事ができる。
このとき文字列sと文字列pの距離を最小にせよ。
ここでsとpの距離とは、pとsの全ての長さ|p|な部分文字列とのハミング距離の和である。
長さが等しい文字列同士のハミング距離とは、２つの文字列において文字が違うような位置の数である。

制約

1 <= |s| <= 100000
1 <= |p| < |s|
0はどちらか一方の文字列にしか現れない。

解法

w = |s|-|p|+1
としたとき、長さ|p|なsの部分文字列はw個ある。
mode_s[i] = s[i-w+1:i]における最頻値、
mode_p[i] = p[i-w+1:i]における最頻値とする。
ただし区間が文字列の外にはみ出るときははみ出ないように区間を縮めるものとする。

s[i]=0の場合、s[i]はmode_p[i]にすれば良く、
p[i]=0の場合、p[i]はmode_s[i+w-1]にすれば良い。

残る問題はどのようにスライド最頻値を求めるかだが、
ヒープと配列をうまく用いると出来る。
窓をスライドさせるとき、ある値が１つ追加され、ある値が１つ削除される。
このような更新のあった値を、そのときのタイムスタンプとともにヒープに入れる。
ヒープは頻度が大きいものから取り出されるようにする。
その窓での最頻値を求めるとき、ヒープから取り出した情報が最新のものかどうかを判断して古いものなら捨てるという処理を行えば良い。