スポンサーサイト

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

VK Cup 2012 Round 2

2012/03/25
VK Cup 2012 Round 2

Tags : プログラミング Codeforces 未解決

問題

問題セットの原文はここを参照。

A. Substring and Subsequence

文字列 s, t が与えられる。
x を s の部分文字列, y を t の部分列とする。
x == y となるようなペア (x, y) の選び方は何通りあるか? mod 10^9+7 で。

1 ≦ |s|, |t| ≦ 5000

B. Lemmings

n 匹のレミング ( リスみたいな動物 ) と k 個の崖がある。
レミング i は重さ m[i], 速さ v[i] で特徴付けられている。
崖 i は高さ i・h である。

n 匹のうち k 匹のレミングがそれぞれ異なる崖に上る。
上りきったとき、低い崖から順にレミングの重さが非減少順になっていないといけない。 ( つまり、重いレミングほど低い崖に割り当てられないといけない )
最後のレミングが崖を上りきるまでの時間を最小化せよ。

1 ≦ k ≦ n ≦ 10^5
1 ≦ h ≦ 10^4
1 ≦ m[i], v[i] ≦ 10^9

C. Conveyor

長さ 2L のベルトコンベア ( L は表面, L は裏面 ) があって、n 個のチョコレートがコンベアに張り付いている。
コンベアの回転速度は v1。
自分はコンベアの表面のランダムな位置から ( コンベアの回転方向と同じ方向に ) 速度 v2 で走り出して、コンベアの表面の端まで行ったらコンベアから降りる。自分の位置と重なったチョコレートを拾うことができる。
「チョコレートをちょうど i 個拾う確率」 をすべての i = 0, 1, ..., n について求めよ。

1 ≦ n ≦ 10^5
1 ≦ L, v1, v2 ≦ 10^9

解答

A.
DP。
まず愚直な O(n^3) を書いてから、その式をにらんで計算量を落とした。
めちゃくちゃ時間かかった。苦手。
http://www.codeforces.com/contest/163/submission/1651817

B.
最大値の最小化なので、テンプレどおり答えについて二分探索する。
最後のレミングが崖を上りきる時刻を固定してしまえば、それぞれのレミングがどの高さの崖まで登ることができるかが計算できるので、軽いレミングから順にできるだけ高い崖に割り当てていけばいい。
http://www.codeforces.com/contest/163/submission/1415554

C.
とりあえず、コンベアをまっすぐに引き伸ばして、自分はある区間だけを走ると思えばいい。
さらに、コンベアは止まっていると思っていい。その分、自分の速度を調節する。
すべての始点 ( チョコレートの位置 ) から調べ始めると O(n^2) かかってダメだけど、自分の走る区間の長さをコンベアの左から右にスイープしていく感じでやれば、O(n) でできる。尺取法にも似ている。
http://www.codeforces.com/contest/163/submission/1417275
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。