isa@procon

AOJ 1020 Cleaning Robot

AOJ | 22:50

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1020

方針

dp[second][pos]で

i+1秒後に次の移動先next_posに移動できるなら

dp[i+1][next_pos] += dp[i][pos] * 0.25;

そうでなければ

dp[i+1][pos] += dp[i][pos] * 0.25;

とすればよい。

以下ソース

続きを読む

ツイートする

落ちたくない一心で迎えた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ぐらいでいいらしいけどよく解らん。

として

だから

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

1050

Unopened

まとめ

最近調子がいい。

ツイートする

こどふぉであったやつ。

oooooo---- 307th 1555->1595(+40)

初めの方はやるだけゲーだったように思える

ICPC形式は初で、初めFileIOであることに気づかなかった。

A.若干問題文読みにくいけどやるだけ。

B.やるだけ

C.結局最後までやるので並び替えは考慮しなくてよし。

if(a[i] > 3*k) res += a[i]-3*k;

else res += a[i]%k;

D.縦横ともに高々50しかないので

O(49C2*2*50*50)で解けると判断。全探索。

E.Grundy数とかわからんと思って飛ばす

F.それぞれの木について直径を求めてその和になる。

木の直径はWFして最大値を求めた。

Eが偶奇な気がして書く→通った！

Fに取り掛かる。初め200個しかないなら結構名前空間に余裕あるんじゃないかと思ったものの、

DFSしたらTLEした。

この時点で残り1時間ちょいで晩飯離脱。

ゲーム系の問題はやっぱり苦手です。

ツイートする

GCJJ　決勝

00:50

予選はC-small/largeを通して通過しました。

決勝は

15pts 49:31 204th

…あああもう少し(4分ぐらい)でTシャツもらえたのになぁ…

B-smallでsubmit debugするんじゃなかった…

A-small/largeを通しました。

隣り合う2本の積の和を最大化すれば良いので、

長いものから順番に正、負方向に交互に置いていけばおｋ。

はじめsmallゲーだろうと思ってsmallはnext_permutation使って全探索して

その後Bに行ったのも敗因の一つではある。

Bはフェルマーの小定理っぽいけど互いに素じゃないときどうなるんだか解らなかった。

smallは(A mod C) == (A mod C)^k mod C となる最小のkを求めれば

(A mod C)^(A^A) = (A mod C)^((A^A mod k) + 1)になるんじゃないかと思ったけど実装できず。

うーん悔しかったなぁ。

C,D,Eは読んだものの取り組みませんでしたとさ。

ツイートする

SRM521 Div.2

00:39

oo-(+2/-0) 826.39pts 20th(Div2) 1151->1276(+125)

祝！Div1昇格！

半年かかりました…(8,9月はインターンのためあまり参加してませんでしたが)

250

i番目(0 <= i <= row.size())までをR,残りをGにする場合の入れ替える数の最小を取る。

始め0 <= i < row.size()とやっててExampleは通ったけど自分で"RR"と入れたら1が返ってきたので

直した。

同じミスしてる人を2人Challengeで落とした。

500

某社のインターンWebテストでありました。

先頭から読んでstackに積む、括弧がtopと合うならpop。

return stack.size();

1000

問題文が読みにくい。

Exmaple読んでも解らなかったけどif and only ifを読んで納得。

Example2の21は7*6/2だし

Example3の66は12*11/2だし

Example4の3は3*2/2だなぁと思ったものの

5は出てこないので謎。

x座標でsortして云々かなぁ？

50分ぐらいあったけど解りませんでした。

---

Div1でもがんばる。

ツイートする

SRM520 Div.2

16:10

1ヶ月ぶりぐらいのSRM

oo-(+0/-0) 598.87 48th(Div2) 1047->1151(+104)

大幅アップ。

250

降順ソート→自分の場所を探して部屋数で割るだけ。

初め(点数,index)のpairを作ってsortとかしようとしてたけど

必要ないことに少しして気づいた。

500

明らかにLuckはHardに使うのが効率いいので一瞬Greedyかと思ったけどそんなことはなかった。

Luckを3問にどう割り振るかは最大で5151通りなので全探索できると判断。

→Passed

1000

YYY,YYN,YNN,NNNについてそれぞれ(通した数,challengeされた数)が何通りあるか数えて

それでDPっぽい…と思ったんだけどよく解らず。

他の人のコード読んでもDPっぽいことしか解らなかったのでEditorial待ち

かどなたか解説してください…

次回大惨事にならないようにがんばります。

ツイートする