Regionals 2008 :: Europe - Southwestern - 競技プログラミング+αなブログ

Virtual Arenaで唐突に参加者募って練習した。
参加してくださった方ありがとうございます。
実装は比較的軽く教育的で良問だらけだった。

4296 - Bring Your Own Horse

問題

頂点数N、辺数Rのグラフが与えられる。
Q個のクエリが与えられるので、各クエリに対して頂点kから頂点tへのルートの中で辺のコストの最大の最小値を求めよ。

制約

N <= 3000
R <= 100000
辺のコスト <= 1000000
Q <= 1000

解法

それぞれのクエリに対してダイクストラをすると間に合わない。
出来るだけコストが小さい辺を使うということを考えると、最小全域木に含まれる辺だけを考えれば良いことが分かる。
最小全域木に含まれない辺を使うことでルート中の辺の最大値が小さくなることはない。
よって、まず最小全域木を求め、各クエリに対してBFSもしくはDFSをすることでO(R+QN)になる。

4297 - First Knight

問題

m*nのフィールドがある。
各マスから上下左右にのみ動くことが出来、各々について動く確率が決まっている。
フィールドからはみ出すような動きの確率は0となっている。
このとき(1,1)から(m,n)まで動くときの期待値を求めよ。

制約

m,n <= 40

解法

典型的なランダムウォークの問題で、連立方程式を解くことに帰着できる。
しかし普通のガウスの消去法ではO((nm)^3)となり間に合わない。
ところがこの場合行列が2*m+1のband matrixとかになっていて、ガウスの消去法の任意の時点で対角成分付近の2*m+1個以外は必ず0となる。
これを利用して無駄な部分を省き、ガウスの消去法をO(nm^3)にすることによって通すことが出来る。

4298 - Postal Charges

問題

二次元平面に点がある。
各点は[i,i+1)×[j,j+1)（i,jは整数）に含まれているとき、(i,j)に属すると考える。
点pと点qが(i1,j1), (i2,j2)に属するとき i2>i1 かつ j2>j1 の時に限り、pからqに線が引ける。
n個の点が与えられるので、線が引ける全てのペアに対して、その座標間のマンハッタン距離の平均値を求めよ。

制約

n <= 100800
0 <= 座標値x,y < 10
x,yは実数値

解法

点が属する(i,j)は、単純にEPS足してintにキャストすれば求まる。
(i,j)の種類は10×10しかない。
例えば、i2>i1かつj2>j1のとき(i1,j1), (i2,j2)の組だけについてマンハッタン距離の平均を求めることを考えると、
$\frac{\sum_{1<=a<=N,1<=b<=M}(|x_b-x_a| + |y_b-y_a|)}{NM}$
$=\frac{N\sum_{1<=b<=M}(x_b+y_b) - M\sum_{1<=a<=N}(x_a+y_a)}{NM}$
となる。ここで、N,Mはそれぞれ(i1,j1),(i2,j2)に属する点の数を表す。 $x_a$ とかは(i1,j1)に属するa番目の点の座標とかを意味する。
これを応用して、全ての(i1,j1),(i2,j2)の組に対して適用することで求まる。割るのは最後。

4299 - Randomly-priced Tickets

問題

頂点数Nのグラフが隣接行列として与えられる。
各辺のコストは1からRまでの整数が一様分布で割り当てられる。
始点aと終点b, 最大許容コストmによって記述されるクエリがC個与えられる。
各クエリに対して、頂点aから頂点bまでのルート中の辺のコスト合計がm以下になる確率を求めよ。
aからbまでのルートとしては、最も確率が高くなるようなルートを選ぶ。

制約

N<=100
R<=30
C<=1000
m<=10000

解法

各辺のコストを1として、全点対間最短距離を求めておく。
最も確率が高くなるようなルートというのは、この最短距離を達成するようなルートである。
この最短距離をdとすると、d回R面のサイコロを振って、出た目の合計がm以下になるような確率が答えとなる。
これはO((NR)^2)のDPをすれば解ける。
このDPは前処理で求めておけば十分なのだけど、クエリごとにやっても何故か通っていた。

4300 - The Game

4301 - The Merchant Guild

解かないと…

4302 - Toll Road

問題

辺数nの木が与えられる。
辺には負もあり得るコストが割り当てられている。
この辺の部分集合を取るときコストの合計の最大を求めよ。
ただし部分集合に含まれる辺は連結していなければならない。

制約

n <= 100000
-1000 <= コスト <= 1000
頂点はユニークなIDで与えられるので、1~nの番号を持つとは限らない。

解法

コスト最大の部分木を求める問題。
DFSで木DPをすればよい。
子のうち、その子を含んだ部分木の最大コストが正の値を持つ場合のみ使うというふうにする。

4303 - Top Secret

問題

N個の要素を持つ数列が与えられる。
各要素について、その値を左にL回加算、右にR回加算という操作が同時にS回行われる。
最終的な数列の下X桁を求めよ。

制約

3<=N<=1000
S<=2^30
L,R,X<10

解法

1回の操作で、N次元ベクトルからN次元ベクトルへの写像が行われる。
つまり1回の操作をN×Nの行列で表すことが出来る。
さらにS乗することにより、S回の操作を表す行列を求めることが出来る。
しかし普通にやるとO(N^3log(S))となり間に合わない。
この問題の場合、行列が巡回行列となっている。
巡回行列と巡回行列の積は巡回行列であり、巡回行列は1行さえ分かればrotateすることにより全ての行を求めることが出来る。
これを利用し、1行目だけを保持することによってO(N^2log(N))となる。

4304 - Transcribed Books

問題

要素数10の数列aがc個与えられる。
全ての数列は、ある2以上の整数Nに対して、
a1 + ... + a9 = a10 (mod N)
が成り立っているはずである。
このとき、考えられる最大のNを求めよ。
もしそのようなNが無かったり、無限に大きく出来たり、N=1の場合はimpossibleを出力せよ。

制約

c<=1000
ai <= 2^28

解法

各数列に対して、
x=0 (mod N)
という条件に変換できる。
xはNの倍数という事になり、全てのxについての最大公約数を求めると答えになりそう。
実際、最大公約数をgとしたとき,g=0,g=1,あるxに対してx>=gのいずれかが成り立つときimpossible。
そうでなければgが答えになる。

4305 - Wizards

問題

n次多項式Pが与えられる。
Pが重根を持つかどうか判定せよ。
持たないなら"Yes!", 持つなら"No!"。

制約

0<=n<=10
-30<=係数<=30

解法

Pが重根を持つことの必要十分条件は、PとP'が共通根を持つこと。
つまり、PとP'の最大公約数が１次式以上ならばPは重根を持つことになる。
最大公約数はユークリッドの互除法を使うが、doubleでやると誤差か何かで死ぬ。
係数で割るタイミングで実数にならないように注意しながら、long longで扱うと良い。
このとき最後に係数の最大公約数で係数を割っておかないとオーバーフローで死ぬ。
シルベスター行列 - Wikipediaを使っても出来るらしい。