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 を求めることに帰着される.これは元の問題と相似なのでよい.

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/52-868c5465

この記事にトラックバックする(FC2ブログユーザー)

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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