社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。
2012-04-25SRM541 Div1
- 250:234.52, 550:292.65, 1000:Opened, score:527.17, rank:29, rating:2274(+104)
- 特段普段と変わらない気がしたのだがなぜか順位は良かった
SRM541 Div1 250 AntsMeet
コーディングフェーズ
任意の蟻のペアで衝突判定をして、時間の早い順に並べて、死んだ蟻を取り除きながら真の衝突判定をする
とか思ったけどあまりにも面倒そうだったので他の手段を検討
単純なシミュレーションで間に合うことに気づいたので書く
サンプル合った
提出
チャレンジフェーズ
ボロボロと周りが落とされていくんだが全然何が悪いのか分からない
どうやら座標を2倍していない人がたくさんいたらしい
サンプルにそういう例があるのでまさか2倍せずに(or 0.5刻みにせずに)提出してる人がいるとは思っていなかった・・・
ソースコード
class AntsMeet { public: int countAnts(vector <int> x, vector <int> y, string dir) { int res; int n=x.size(); for(int i=0; i<n; i++) { x[i]*=2; y[i]*=2; } int dis[52]={0}; for(int t=0; t<10000; t++) { for(int i=0; i<n; i++) { if(dir[i]=='N') y[i]++; if(dir[i]=='E') x[i]++; if(dir[i]=='S') y[i]--; if(dir[i]=='W') x[i]--; } for(int i=0; i<n; i++) { if(dis[i]) continue; for(int j=i+1; j<n; j++) { if(dis[j]) continue; if(x[i]==x[j] && y[i]==y[j]) { dis[i]=dis[j]=1; } } } } res=0; for(int i=0; i<n; i++) if(!dis[i]) res++; return res; } };
SRM541 Div1 550 AkariDaisukiDiv1
コーディングフェーズ
上限が1000万だから単純なループにする問題ですかね
だとすると、Xに対してWaaiとかAkariとかくっつけた時に解が増える増分だけ調べればいいのでは
これって、Xの先頭はWaaiWaaiWaai...になるし、後ろは...DaisukiDaisukiDaisukiになるから、50回以上繰り返せば増分は一定の値に収束するっぽい
Xが短い間は全探索して、ちょっと長くなったらprefixとsuffixだけ覚えて、50回以上になったらあとはループするだけ
やるだけ・・?
なぜ550
書く
増分の計算かなりめんどい
思ったよりは大変だった
できた
提出
ソースコード
const int MOD=1000000007; class AkariDaisukiDiv1 { public: int countF(string w, string a, string d, string S, string F, int k) { int res; string x=S; string px, sx; ll cnt=0; int inc=0; for(int i=0; i<min(51, k); i++) { if(px.empty()) { x=w+x+a+x+d; if(x.size()>=F.size()) { cnt=0; for(int j=0; j+F.size()<=x.size(); j++) { if(x.substr(j, F.size())==F) cnt++; } } if(x.size()>50) { px=x.substr(0, 50); sx=x.substr(x.size()-50); x.clear(); } } else { inc=0; string tx=sx+a+px; for(int j=sx.size()-F.size()+1; j<=sx.size()+a.size()-1; j++) { if(tx.substr(j, F.size())==F) inc++; } px=w+px; sx=sx+d; for(int j=0; j<w.size(); j++) { if(px.substr(j, F.size())==F) inc++; } for(int j=sx.size()-d.size()-F.size()+1; j+F.size()<=sx.size(); j++) { if(sx.substr(j, F.size())==F) inc++; } px=px.substr(0, 50); sx=sx.substr(sx.size()-50); cnt=(cnt*2+inc)%MOD; } } for(int i=51; i<k; i++) { cnt=(cnt*2+inc)%MOD; } res=cnt%MOD; return res; } };
Praveen2012/11/14 15:22You've really captured all the esstenials in this subject area, haven't you?
lltwektgdji2012/11/17 00:38s3e55e <a href="http://weadgecnprbz.com/">weadgecnprbz</a>
zkwvhwi2012/11/17 10:47mzuI7w , [url=http://amjymbwsqtpw.com/]amjymbwsqtpw[/url], [link=http://jtoocgzxmaus.com/]jtoocgzxmaus[/link], http://uoyfejtwsvcz.com/