2017-10

Latest Entries

スポンサーサイト

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

Univ. of Aizu ICPCPC 2011 TT 18 DIV1

UVa のジャッジサーバが落ちていたため練習会としては流れた.
問題は選ばれていたので 3 問読んで 3 問書いた.後で送ったら一発で通った.

E: Non-Decreasing Prime Sequence (UVa 11669)


有限非減少素数列の weight とは,各項の積のこと.
weight が A 以上 B 以下のうち,「長さ昇順 → 辞書順」で K 番目にくるものを求める.
2 <= A <= B <= 1,000,000,5,000 ケース.

要は A 以上 B 以下の整数を素因数の様子でソートしたときに K 番目.
cntp[x] で x の素因数の個数,minp[x] に x の最小の素因数を覚えさせれば,
a が b より先に来る条件は cntp[a] < cntp[b] or (cntp[a] == cntp[b] and minp[a/g] < minp[b/g]),ただし g = gcd(a, b).
これを用いると O(N (log N)^2) で N までソートできる.
その後,√N 個くらいずつに区切って普通の大小でソートしたものを持っておくと,各クエリに対して O(√N log N) で処理できる.

どう高速化しようか悩んで結構時間を使ってしまった.

F: Dynamic Frog (UVa 11157)


一直線上の川をカエルが往復する.
岩が N 個あり,大きい岩は何度でも踏めるが小さい岩は一度しか使えない (つまり行きと帰りのいずれか).
最大ジャンプ幅を最小化する.
N <= 100.

行きと帰りを同時に左端から作っていく DP.
dp[i][j] から,dp[k][j] と dp[i][k],ただし k >= max{i, j},に配る.
小さい石について dp[i][i] を捨てる.

G: Through the Desert (UVa 11935)


燃料を満タンにして車が砂漠の道を行く.
途中で,燃料の消費率,壊れて燃料がリークする,燃料補給,修理といったイベントが起こる.
必要な燃料タンクの最小値を求める.

二分探索,シミュレーション.

コメント

コメントの投稿


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

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/6-015216e6

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

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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