SRM541 Div2

9thでした。Hardが簡単めだったので、解きたかったです。

Easy(215.96/250)
わぁい撃墜 あかり撃墜大好き(Easyでは撃墜していません)
色々面倒なだけ。

class AkariDaisukiDiv2{
public:
	int countTuples(string s) {
		int len = s.size(),ans=0;
		for(int i = 1; i < len-1; i++){
			for(int j = i+2; j < len-1; j++){
				if(s[i]==s[j]){
					for(int k = 0; j+k<len-1 && i+k<j-1; k++){
						if(s[i+k]==s[j+k])ans++;
						else break;
					}
				}
			}
		}
		return ans;
 	}
};

Medium(293.28/500)
座標が半整数の点で衝突する場合があるので、座標を2倍しておく。
2倍しなくてもサンプル通るので、2倍してない(且つ、0.5の点での衝突を考慮してない)ソースは撃墜しておく。

const int INF = 1e7;

class AntsMeet{
public:
	int countAnts(vector <int> x, vector <int> y, string s) {
		int n = s.size(),ans = n;
		for(int i = 0; i < n; i++){
			x[i] <<= 1;
			y[i] <<= 1;
		}
		
		for(int i = 1; i <= 4000; i++){
			map<pair<int,int>,int> g;
			for(int j = 0; j < n; j++){
				if(x[j]==INF)continue;
				if(s[j]=='N'){
					++y[j];
				}
				if(s[j]=='S'){
					--y[j];
				}
				if(s[j]=='E'){
					++x[j];
				}
				if(s[j]=='W'){
					--x[j];
				}
				++g[make_pair(x[j],y[j])];
			}
			
			for(int j = 0; j < n; j++){
				if(g[make_pair(x[j],y[j])]>=2){
					ans--;
					x[j] = y[j] = INF;
				}
			}
		}
		
		return ans;
 	}
};

Hard(-/1000)
あからさまにNails
合ってるか分からないけど、submitしておけば良かった。間違ってました。(範囲を超えるのと、制約を読み間違えて縦と横の長さが等しいと勘違いしていたこと)

解法は合っていたので、解けなければならなかった。
正しいソース

short g1[3500][3500],g2[3500][3500];

class NonXorLife{
public:
	int countAliveCells(vector <string> s, int K) {
		int ans = 0;
		int len = s.size(),len2 = s[0].size();
		
		for(int i = 0; i < len; i++){
			for(int j = 0; j < len2; j++){
				if(s[i][j]=='o'){
					g1[i+K+1550][j+1550] = K+1;
					g2[i-K+1550][j+1550] = K+1;
				}
			}
		}
		
		for(int i = 3395; i; i--){
			for(int j = 1; j < 3395; j++){
				g1[i][j] = max(max((int)g1[i][j],(int)g1[i+1][j]-1),max((int)g1[i+1][j-1],(int)g1[i+1][j+1])-1);
			}
		}
		
		for(int i = 1; i < 3395; i++){
			for(int j = 1; j < 3395; j++){
				g2[i][j] = max(max((int)g2[i][j],(int)g2[i-1][j]-1),max((int)g2[i-1][j-1],(int)g2[i-1][j+1])-1);
			}
		}
		
		for(int i = 0; i <= 3395; i++){
			for(int j = 0; j <= 3395; j++){
				if(g1[i][j]||g2[i][j])ans++;
			}
		}
		
		return ans;
 	}
};

Score 709.24 (challenge:50*4)
Rating 1128 -> 1281