Hatena::Grouptopcoder

灰コーダーのゆとり日記

2012-07-09

SRM549 Div2

00:07

とりあえずTopCoder部に登録してみました。

まだどういうものかちゃんと理解していません…。

Twitter:kpg_yaruo

TopCoder:iga_c

です。

コンテスト参加記と初心者向けにしかならない事をちょくちょく書いていこうかなーと思います。

という訳で今回の参加記

TopCoder SRM549 Div.2

o-- +50/-0 125pt 448th

Rating 531→555(+24)

Easy:

問題文→http://community.topcoder.com/stat?c=problem_statement&pm=11964

マジシャンが横に並んでるコップのうちどれか1個に入れて、隣り合ってるカップの入れ替えを行う。

カップを入れ替える際にボールが入ってるカップを入れ替えた時のみカウント。

n回回した後一番ボールが入ってる確率の高いカップはどれ?同じ確率なら数字の低い順に出力しろ

って問題でした。

最初は理解できずDPとか使っちゃった上にバグ付きコードを提出してしまいました。

後々バグに気づき、再提出をしました。

よく読むと

0回 o.. .o. ..o

1回 .o. o.o

2回 o.o .o.

3回 .o. o.o

n回 o.o .o.

の繰り返しになっていました。

ということで入れ替えが0回ならボールがある場所、入れ替えるならぐるぐる回して0か1にして返せばACでした。

o.oは同じ確率なら数字の低い順というルールで0で返します。

Medium:

問題文→:http://community.topcoder.com/stat?c=problem_statement&pm=11965

これがよくわからなかった。

・The apex of the top cone must be strictly above the apex of the bottom cone. I.e., when the top cone is placed on top of the bottom cone and released, their apexes must not touch.

・Some part of the bottom cone must remain visible to form the brim of the hat. (Otherwise, the hat would look like a simple cone, not like a wizard hat!)

・上の円錐の頂点の上に下の円錐の頂点が触れてるのはだめ(上にあるのも?

・下の円錐の一部は見えていないといけない

それでsampleの

{4,4}

{4,3}

{5,12}

{5,4}

Returns: 1

The only way to produce a wizard hat is to use the top cone 1 (height 4, radius 3) and the bottom cone 0 (height 5, radius 5).

が何故4-3 - 5-5だけしか成立しないのかがわからなかった。

そもそそも上の円錐小さくね?ってのと4-3がいいなら4-4でもおkな気がして…。

TopCoderのサイトチェックしたらDiv1Easyと同じっぽいんで読んでみます。

Hard:

開いてません!1000とか怖い!


以上です。緑目指して頑張りたいです。

ゲスト