SRM diary(Sigmar)

• 250:234.52, 550:292.65, 1000:Opened, score:527.17, rank:29, rating:2274(+104)
• 特段普段と変わらない気がしたのだがなぜか順位は良かった

SRM541 Div1 250 AntsMeet

SRM541, Div1 | 01:12 |

Problem Statement

コーディングフェーズ

任意の蟻のペアで衝突判定をして、時間の早い順に並べて、死んだ蟻を取り除きながら真の衝突判定をする

とか思ったけどあまりにも面倒そうだったので他の手段を検討

単純なシミュレーションで間に合うことに気づいたので書く

サンプル合った

提出

チャレンジフェーズ

ボロボロと周りが落とされていくんだが全然何が悪いのか分からない

どうやら座標を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

SRM541, Div1 | 01:12 |

Problem Statement

コーディングフェーズ

上限が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;
	}
};