Hatena::Grouptopcoder

isa@procon このページをアンテナに追加 RSSフィード

2011-10-26SRM522 Div.1

落ちたくない一心で迎えたDiv1復帰後1回目のSRM

ox- (+0/-0) 234.09pts 197th(Div.1)

Ratingは1276->1371(+95)

安全圏まで上がりました。

250

openした瞬間一瞬Grundy数とかそういう方向かと思ったけど問題を読む。

連続するA,Bは1つとしても同じなのでsampleからそれぞれの個数と勝敗を書いてみる。

->多い方が勝ってるっぽい。

ルールから改めて考えると、自分のcellが残れば勝ちなので相手のcellを潰せばいい、自分のcellを潰すことに価値はないのでそういう行動はしないはず、と考えて

それぞれの個数を数えて

a>=b?cout << "Alice" << endl:cout<< "Bob" << endl;

とした。challengeで他の人を見たら

if(cells[0] == 'B' && cells[cells.size()-1]){
    cout << "Bob" << endl;
}else{
    cout << "Alice" << endl;
}

というのも見た。頭いい。

500

TLE解しか書けず。

cの前後いくつかを2つの積に分けてa,bとの差を見ていくのか、

a,bを少しずつずらして誤差最小のCを見つけていくのかで悩んだ。

結局a,bを合計kずらすときの誤差最小のCをとって、

k+取れた最小の誤差を新しいkの上限とする方法で書いてSampleは通ったものの結局

{1,1,10^9}とかいうのがTLEするのでだめ。

TL追ってるとCは+-2000ぐらいでいいらしいけどよく解らん。

A*B=Cとして

(A+p)(B+q) = AB + pB + qA + pq

           =C + pB+qA+pq

だから

p+q+pB+qA+pq

を最小化すればいいとか考えたけど無理ゲだった。


1050

Unopened

まとめ

最近調子がいい。

MarikoMariko 2013/02/16 22:58 How neat! Is it relaly this simple? You make it look easy.

MarikoMariko 2013/02/16 22:58 How neat! Is it relaly this simple? You make it look easy.

nnzwrfzuinnzwrfzui 2013/02/17 21:17 GxhRsl <a href="http://ldyifqhzmauq.com/">ldyifqhzmauq</a>

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/isa_rentacs/20111026