スポンサーサイト

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

Codeforces Round #125 (Div. 1)

2012/06/23 00:30 ~ 02:30
Codeforces Round #125 (Div. 1)

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

結果

A: AC
B: AC
C: WA
D: -
E: -
22052139


問題

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

A. About Bacteria

x 匹のバクテリアは一秒後には k・x + b 匹に増える。
今、1 匹のバクテリアから始めて、n 秒後に z 匹になった。
t 匹のバクテリアから始めると、何秒後に始めて z 匹以上になるか?

1 ≦ k, b, n, t ≦ 10^6

B. Jumping on Walls

長さ n のビルが向かい合って建っている。
ビルを登っててっぺんまで行きたい。
自分は最初左のビルの一番下にいる。
できる動作は、
・ 一マス登る
・ 一マス下る
・ もう一方のビルのちょうど k マス高いところに飛び移る
のいずれか。
三つめの動作によっててっぺんより上に行けたときもゴールとみなす。
ただし、ビルのいくつかのマスは壊れていて、そういうマスには進入できない。
一つの動作をするたびに下から水が一マス分せり上がってきて、水に触れると失敗。
てっぺんまで行けるかどうか判定せよ。

1 ≦ n, k ≦ 10^5

C. Delivering Carcinogen

二次元平面に、ロケットと惑星と太陽がある。
太陽は原点に固定されている。
惑星は太陽を中心とする円軌道を描きながら等速度で回っている。
自分はロケットに乗っていて、できるだけ早く惑星に着きたい。最短で何秒かかるか?
ただし、どの時点においても太陽とロケットの距離が r 以下になってはいけない。

r < 惑星の初期位置
r < ロケットの初期位置
惑星の速度 < ロケットの最高速度

解答

A.
z はものすごく大きい数になるので、問題文どおり素直に計算しようとすると TLE する。

見方を変えて、
「一匹のバクテリアから始めて、何秒後に t 匹を超えるか」
を求める。
a 秒後にはじめて t 匹を超えたとする。
n 秒後に z 匹を超えているので、a 秒後をスタート地点だと思うと、そこから n-a 秒後に z 匹を超えたと見ることができる。
( バクテリアの増え方が単調であることが利いている。 )

a は素直な方法で計算できるので、答えが求められる。

最初は全然思いつかなかった。発想の転換であっさり解ける良問だと思った。

※ "超えた" と言ってるところは "以上" かもしれないし、+-1 くらいずれてるかも。細かいところまでちゃんと考えてない。

O(t)
http://www.codeforces.com/contest/198/submission/1820431

B.
ふつうの BFS。
Div.1 B にしては拍子抜けするくらい簡単。

O(n)
http://www.codeforces.com/contest/198/submission/1815896

C.
まず、ロケットの速度 > 惑星の速度という制約によって、二分探索が適用できることがわかる。
実際、ある時間で惑星に到達できれば、それより長い時間でも惑星に到達できる。惑星にべったりくっついていけばいい。

なので、時間を固定、つまり惑星の位置を固定したときに、ロケットと惑星の間の最短距離が求められればいい。
幾何パート。
これは UVa 10180 と同じ問題で、図にあるように太陽の弧を使うケースと直接線分で結ばれるケースを両方考えればいい。

アイデア自体は、いつもの Div.1 C に比べれば簡単なほうだと思った。
自分の幾何ライブラリには点から円に引いた接線を求める関数がなかったので、バグと格闘しながらコンテスト中に書いていた。
結局、角度の処理を間違えて system test で落ちてしまった。
やっぱり幾何はライブラリがないとダメだ。
あと、正解者は意外と少なくて 30 人くらいだったので、ロシアの人々は幾何に弱いのだなぁとも思った。

O(k) ( k は二分探索の反復回数 )
http://www.codeforces.com/contest/198/submission/1822066
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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