Entries

スポンサーサイト (この記事を編集する[管理者用])

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

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1913-6fbdc7ba
この記事にトラックバックする(FC2ブログユーザー)

SRM503 DIV1 参加記録 (この記事を編集する[管理者用])

2011年04月17日01時02分から.
[summary]

Assignment

250-500-1000の標準セット.
青いっぱいの部屋.

EASY

何種類かパンがある.
各種類ごとに閾値があって,それより長く焼くと焦げ,それより短いと焼けない.
焼けなかったパン (50個以下) の焼いた時間と,焦げたパン (50個以下) の焼いた時間が与えられる.
どの種類のパンも,最低1枚は焼けず,最低1枚は焦げた.
最小で何種類のパンがあったかを求める問題.ありえないならそれを指摘する.
同じ時間だけ焼いたパンは存在しないとする.

問題文長い.でも絵が多い.
なんか入力と絵とサンプル見たらだいたい意味理解できた.
交互に並べ替えるのかな?
うお,最後のサンプルの答え2かよ?
最後が2なら,全部2でいけるんじゃないの?
えーっと,2で行けるのか?
1種類目は一番時間の小さい焼けなかったの,2種類目は一番時間の大きい焦げたのを起点にすればいける.
じゃ,焼けなかった|焦げた がはっきり分けれてたら1で,そうでなければ2.
後,不可能があるな.
一番小さいの同士,一番大きいの同士比べて,焦げたほうが時間少なければ不可能でいい.
よし,書いた.提出.
なんか,変な勘違いとかしてないか?
もう1回ちゃんと考えろ.
良さそう.
次行こう.

MEDIUM

2次元平面上のN個 (50以下) の街とM個 (50以下) の村の座標が与えられる.
最初は道はなく,M個の村は,どの街とも隣接していない.
以下の作業を行ったとき,できる道の総距離の平均値を求める問題.
 ・まだ街に移動できない村を1つ選ぶ これをXと書く
 ・街か,街に移動できる村の中から,Xに一番近いものを選び,その間に道をつくる
 ・街に移動できない村がある限りこれを繰り返す

えっと,ビットDP…ではない.
これは,どうせ期待値だから線形性だ.
各村ごとに独立に計算しよう.
一番近い村が先に選ばれてる確率は1/2.
2番目に近い村が先に選ばれてる確率は…,1/2*1/2で1/4?違う気がするが.
取り敢えず,書く.
やっぱり違った.
えっと,どうなる….
あ,一番近い村は,今考えてる村より後に選ばれるのが確定している.
だから,2番目に近い村は
 2番目 考えてるの 一番近い
 考えてるの 2番目 一番近い
 考えてるの 一番近い 2番目
のどれかだから,考えてるのより先に来るのは,1/2 * 1/3か.
後は,1番目~k番目が先じゃなかったときの確率に1/(k+1)みたいなのをかけていけばいいだけ.
今度はサンプル通った.サブミット.
一応考え方合ってるかどうかもう一度確認して次へ.

HARD

無限に高いビルが2つ建っている.
階と階の間は2メートルで,ビルとビルの間は2以上10以下の偶数メートル.
地面と連結な部分から,傾き-1か+1の階段を作っていく.
階段を作る際は,階段かビルにぶつかるまで伸ばさなければいけない.
それぞれのビルに非常口を作りたい階が与えられるので,それを地面と連結にしたい.
階段の長さに応じてコストが与えられるので,最小コストを求める問題.
問題文の絵が参照のこと.

うーん,どうするんだ.
一番上の部分がどうなってるかでDPかなぁ.
それより下で非常口作れてなかったのは,適当に引けば良さそう.
書いてみよう.
書いてる途中に気づく.適当に引けば良さそう,ってそんなこと全然ないよ!
でも,取り敢えず,それは後で考えるとして,取り敢えず嘘解法を書く.
最悪,それも,DPっぽくできるし.
….
嘘解法すら仕上げられなかったorz

Challenge

EASYで何かミスってる人いないかと思ったけど見つけられなかった.

System tests

EASYとMEDIUM通る.
早解き勝負でまぁまぁいい成績.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1913-6fbdc7ba
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。