2017-11

Latest Entries

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

POJ

過去に送って通らなかったらしい問題たちに再挑戦.

POJ 2968: Necklace


平面上の N 個の点が与えられるので,それらを中心に円を描く.i 番目と i + 1 番目あるいは 1 番目と N 番目は交わり,その他の組は交わらないように半径 (0 以上 10^4 以内) を決める.外接する距離から 10^(-5) 以内の場合は都合よく判定される.
2 <= N <= 100,-10^3 <= (各座標) <= 10^3.

半径を変数,目標関数を 0 として LP を解かせたら通った.

LP の式 Ax <= b において b に加える微小な値を 1e-6 としたら TLE し,1e-8 としたら WA し,1e-7 としたら通った.原因は不明.TLE は LP が誤差に弱いための無限ループの可能性あり.

POJ 1311: Doing Windows


4 個の長方形があり,サイズは W[i] * H[i] である.これらを縦横の長さが整数であるように相似に拡大あるいは縮小し,あるサイズの長方形に隙間なく敷き詰めることが可能かどうか判定する.

まずサイズを最大公約数で割っておく.長方形が 4 個以下なので,縦または横に割ることで,ある 1 個か 2 個が切り離される配置のみがありうる (5 個だとこれは偽).どちらの場合も拡大比は定まるため,再帰で全部の切り離し方を試せばよい.
計算は 64-bit で通った.

POJ 1508: Skyscraper Floors


F 階建ての建物があり,E 個のエレベーターがある.エレベーター i は Y[i] + k X[i] (k は非負整数) に止まる.A 階から B 階までエレベーターのみで行けるかどうかを判定する.
1 <= F < 50,000,000,0 < E < 100,X[i] > 0,Y[i] >= 0.

エレベーター i, j が同じ階に止まるかは連立方程式を解いて max{Y[i], Y[j]} 以上の最小の解に注目すればわかる.あとは BFS などをすればよい.

b に m の倍数を加えて y (> b) 以上にする際,b += (y - b + m - 1) / m * m; の * m を忘れて WA.また,0 階から F - 1 階が使えるように思える問題文だが,F 階も使える.

POJ 1639: Picnic Planning


いくつかの家と Park があり,それらを結ぶ n 個の距離付きの道がある.何人かの家から車を出し,何人かを連れて Park へ行く.どこかの家で集まって,車を 1 台以外放置して合流することもできる.車の容量は無制限.Park へ行ったら戻れない.Park には高々 s 台の車が入れる.全員が Park へ行くための運転距離の総和の最小値を求める.解の存在は保証されている.
(家の個数) <= 20.

Park の次数が s 以下という制約付きの最小全域木を求めればよい.まず辺をコストでソートし,Park に接続する辺に印をつける.s は必要ならば小さくし,使用を許すちょうど s 個の辺の組み合わせすべてに対して Kruskal 法を行う.

POJ 2124: Crankshaft


N 個の多角形状の十分薄い均一な板が重なっている.重心の座標を求める.
1 <= N <= 100,3 <= (多角形の頂点数) <= 200.

分割したときの重心は座標の加重平均で求まる.符号付き三角形分割をしてよく,三角形は単体なので重心は座標の平均.

-0.0000 出力で WA.

POJ 3164: Command Network


平面上の N 個の点が与えられ,M 個の組 (i, j) に対して点 i から点 j への単方向の道がその距離のコストで作れる.1 番目の点からすべての点へ行けるようにするための最小コストを求める.不可能ならば指摘.
N <= 100,M <= 10,000.

最小根指定有向木.隣接行列で実装して O(N^3).

入ってくる辺で最小コストのものを求める際に,隣接行列の対角も見てしまった.入力時に INF を入れておいても,気にしないで書くと 0 の強連結成分縮約後に対角に 0 が入る.

POJ 3530: A Modular Arithmetic Challenge


正の整数 M, D, L, R に対し,L <= (Dx mod M) <= R なる最小の非負整数 x を求める.存在しなければ指摘.
1 <= M, D, L, R <= 2,000,000,000.

互除法の類似で再帰的に解ける.
R を M - 1 以下し,L > R ならば解なし.D は予め mod M をとってよい.D = 0 のときは L = 0 かで判定.L <= Dx <= R なる x が存在するときはそれが解.
そうでないときは k = floor(L / D) として Dk < L <= R < D(k + 1) である.y = x - k とおいたとき,L - Dk <= (Dy mod M) <= R - Dk なる最小の y を求めればよいが,これは Dy = Ma + b としたときの a の最小化であるため,Ma = Dy - b = D(y - 1) + (D - b) と書いて,D(k + 1) - R <= (Ma mod D) <= D(k + 1) - L なる最小の a を求めることに帰着される.これは元の問題と相似なのでよい.

スポンサーサイト

POJ

POJ 3415: Common Substrings


文字列 A, B に対して,k >= K かつ A[i .. i + k] = B[j .. j + k] なる組 (i, j, k) の個数を求める.
1 <= K <= |A|, |B| <= 100,000,文字はアルファベット.

A ~ '!' ~ B の Suffix Array と高さ配列を構築.長さ k の部分文字列として共通なものは LCP の長さが k 以上で繋がっている各部分に対して,A 由来が a 個,B 由来が b 個であれば a * b 個カウントされる.k の降順に考えれば,Union-Find と同時に a, b も管理していくことができる.
Suffix Array の構築は O((|A| + |B|) (log (|A| + |B|))^2) を用いた.2.5 秒.
スタックを用いて O(|A| + |B|) でも解ける (たぶん).

実践的プログラミング 2011/06/06

POJ 1375: Intervals


平面上に,点光源と N 個の円が与えられる.円は光源より下にある.y = 0 上にできる影を互いに交わらない区間の和集合として出力する.
N <= 500.

円に点から引いた接点,直線と直線の交点でそれぞれの影は求める.pair でソートして,1 つだけ現在作りかけの区間を持ちつつなめていく (右端を max していく,離れたら出力).

右端を単に書き換えていて,影が別の影に含まれる場合に落ちていた.

霊体物質化能力


N 体の幽霊がいて,それぞれは n[i] 角形.ある点に人がいて,人から距離 r 以内の幽霊は実体化される.2 体の実体化された幽霊が共有点を持つ場合,それらは衝突し,衝突した幽霊の組のうち面積が最大でないものがやられる.r が 0 から連続的に増えていくとき,最初に衝突が起こるときにおける,消える幽霊をすべて出力する.
N <= 100,n[i] <= 20.

点と多角形の距離および,多角形と多角形が共有点を持つかを判定する.前者は点が内部に含まれているならば 0,そうでないならば各辺との距離を調べて O(n[i]).後者は一方の 1 頂点が他方に含まれているならば YES,そうでないならば各辺の組を調べて O(n[i]n[j]).
準備ができたら,距離が近い多角形から順に加えて衝突するかを見て,最初の衝突があったら r が同じ値である限り範囲を伸ばし,衝突するものを併合して連結成分での面積の最大値を調べる.

衝突しないものまで併合してしまった.また,人が幽霊に含まれるケースを忘れていた.

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。