SRM551 Div1

今回は問題が簡単でした。

Easy(123.68/250)
左から右に動かした時に、ある点から左に繋がっているアルファベットの個数と、右から左に動かした時に、ある点から右に繋がっているアルファベットの個数を計算して、合計が大きくなるものを求めました。

int l[26][50][2501],r[26][50][2501];

class ColorfulChocolates{
	
public:
	int maximumSpread(string s, int sw) {
		memset(l,0,sizeof(l));
		memset(r,0,sizeof(r));
		int ans=1,len=s.size();
		if(len==1)return 1;
		for(int k = 0; k <= 2500; k++)l[s[0]-'A'][0][k]=1;
		for(int i = 1; i < len; i++){
			for(int j = 0; j < 26; j++){
				if(j==s[i]-'A'){
					for(int k = 0; k <= 2500; k++){
						l[j][i][k]=l[j][i-1][k]+1;
					}
				}else{
					for(int k = 0; k <= 2500; k++){
						for(int m = 1; m <= l[j][i-1][k]; m++){
							if(k+m<=2500){
								l[j][i][k+m]=max(m,l[j][i][k+m]);
							}else break;
						}
					}
				}
			}
		}
		
		for(int k = 0; k <= 2500; k++)r[s[len-1]-'A'][len-1][k]=1;
		for(int i = len-2; i >= 0; i--){
			for(int j = 0; j < 26; j++){
				if(j==s[i]-'A'){
					for(int k = 0; k <= 2500; k++){
						r[j][i][k]=r[j][i+1][k]+1;
					}
				}else{
					for(int k = 0; k <= 2500; k++){
						for(int m = 1; m <= r[j][i+1][k]; m++){
							if(k+m<=2500){
								r[j][i][k+m]=max(m,r[j][i][k+m]);
							}else break;
						}
					}
				}
			}
		}
		for(int i = 0; i < len-1; i++){
			for(int j = 0; j < 26; j++){
				for(int k = 0; k <= sw; k++){
					ans = max(ans,l[j][i][k]+r[j][i+1][sw-k]);
				}
			}
		}
		return ans;
		
 	}
};

Medium(Failed System Test/450)
消すYの個数をコストとして、0からN-1までの最短距離を求める問題とみなすことが出来る。
あとは実装するだけです。
ワーシャルフロイドの実装を間違えて落としました。

int g[50][50];
const int inf = 1<<20;

class ColorfulWolves{
public:
	int getmin(vector <string> s) {
		int n=s.size();
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				g[i][j]=inf;
			}
		}
		for(int i = 0; i < n; i++){
			int c=0;
			for(int j = 0; j < n; j++){
				if(s[i][j]=='Y')g[i][j]=c;
				if(s[i][j]=='Y')c++;
			}
		}
		for(int k = 0; k < n; k++){//kを最初にする
			for(int j = 0; j < n; j++){
				for(int i = 0; i < n; i++){
					g[i][j] = min(g[i][j],g[i][k]+g[k][j]);
				}
			}
		}
		if(g[0][n-1]==inf)return -1;
		return g[0][n-1];
 	}
};

Score 123.68
Rating 1238 -> 1241