UVa 13033 - Jumping Frogs II

Source

An Asian Preliminary Regional(20151205)
(ICPC Dhaka 2015 Preliminary)
UVa 13033

問題概要

無限に続くマス目があり,その中に $N+1$ 個の区間
 $1$ から $X_1$ まで
 $X_1+1$ から $X_2$ まで
 $\vdots$
 $X_{N-1}+1$ から $X_N$ まで
 $X_N+1$ から $10^9$ まで
とある.
$F$ 匹のカエルがいて,$i$ 匹目のカエルは最初マス $P_i$ にいて,各時間 $V_i$ だけ右のマスに移動する.
全てのカエルが同じ区間に属するような最初の時間を求める問題.
存在しないならそれを指摘する.

解法

各区間について,各カエルがその区間に滞在する時間の区間を求めて,最小値を取る,ということをやっても通った.
時間計算量は $O(FN)$ で,多分想定解法ではない.
高速な方法は多分,シミュレーションをする.
カエルの位置でソートしておき,先頭のカエルと最後のカエルが最初に同じ区間になる時間を探せば良い.
次にどこかのカエルがどこかのカエルを抜き去るか,先頭のカエルか最後のカエルの属す区間が変わるような最初の時間を求めて,その時間まで飛ばす,という感じのシミュレーションをすれば良い.
こうすれば多分,時間計算量 $O((F^2+N) \log F)$ 程度な気がする.

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります.


Current time: 2017年07月24日15時49分32秒
Last modified: 2015年12月16日01時27分54秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20151205_1
トップページに戻る

Logged in as: unknown user (not login)

ログイン: