Hatena::Grouptopcoder

灰コーダーのゆとり日記

2012-08-17

TopCoder SRM552 Div2

13:02

結果:

SRM552 Div2 ox- +50/-0 238.0pt 95th Rating 555→726(+171)

easy:

買えないマスの周囲4方向のマスをチェックして一番多い所を出力してみた。

こんな感じで黒塗りの部分を調べていく。xxのマスが買えないマス

上:

■■■■■

■■■■■

□□xx□□

□□□□□

□□□□□

下:

□□□□□

□□□□□

□□xx□□

■■■■■

■■■■■

左:

■■□□□

■■□□□

■■xx□□

■■□□□

■■□□□

右:

□□□■■

□□□■■

□□xx■■

□□□■■

□□□■■


買えないマスが端っことかにある場合は無視しちゃう。

例えば(0,0)なら

下:

xx□□

■■■

■■■

右:

xx■■

□■■

□■■

だけ調べればいい。


medium:

落とされたー。

とりあえずNを3で割った余りが1の時は1種類だけ余分にボールを使わないといけない。

何個三角形を作れるかなので、1種類余分に使う色が変わってもいいってのが嫌らしい…。

通ったらまた追記しようと思います。

2012-07-11

Codeforces Round 129 Div.2

02:59

システムテストが終わったので編集します。

Codeforces Round 129 Div.2 ox-o- +0/-0 1576pt 331位

Rating 1280→1411(+131)

A:

http://codeforces.com/contest/205/problem/A

各町への最短距離を与えるので、何番目のデータが一番早く行けるか答えろ。

複数の最短距離がある場合は移動しない。

データをぶち込んで昇順にsortして0番目と1番目の比較したら終わりました…。

逆に不安になった問題;w;

B:

http://codeforces.com/contest/205/problem/B

配列が与えられて、中身が昇順になるようにしたい。

足りない部分には1を足すことができ、1回で好きな隣り合った配列の中身を+1出来る

最低何回足せば昇順になるようになるか

ちょっと日本語がおかしいので問題文読んでください。

尺取り法チックで書いたんだけどWAでした。

テストケースを見てみたい。

C:

問題文見てやばそうだったからやめたェ

D:

http://codeforces.com/contest/205/problem/D

Div1.Bと同じ問題なのでDiv1の方の解答例を見るといいと思います!

とりあえずカードの色数が多すぎて配列じゃ保存できないのでmap使って出たカード保存。

俺はmap<int,int> m1(表カード),map<int,int> m2(裏カード)みたいな感じで分けましたが、map<int,pair<int,int>>でやってるのみて頭いいなぁと思いました

表と裏が同じなら表のみに、違うなら裏もデータに追加します。

後は出た色の数値をsetに入れておいてm1+m2がnの半分以上かどうかを調べて、半分以上ならvectorにn-m1を入れます。頭いい人はmax(0,n-m1)でやってました!

その後、vectorの中身が0なら作れないので-1,vectorの中身が1個以上あるならソートして0番目の要素の値を出力すればおkです。0以下なら0にしてあげて出力です。

E:

開いてすらいなry


Dは皆似たようなコードだなぁと思ったら結構落ちてたりするのでdiv1組の方の解説を見た方がいいと思われます!

とりあえずレーティングめっちゃ上がって大満足でした!Bをなんとかして通したかった…;

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とか怖い!


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