SRM533 Div2

Easy
(入力の)最後の1文字まで考えないと、「pikapipip」みたいなので落ちます。

class PikachuEasy{
public:
	string check(string s) {
		for(int i = 0,l = s.size(); i < l; i+=2){
			int f = 0;
			if(s[i] == 'p'){
				if(i+1<l && s[i+1] == 'i') f = 1;
			}
			if(s[i] == 'k'){
				if(i+1<l && s[i+1] == 'a') f = 1;
			}
			if(s[i] == 'c'){
				if(i+2<l && s[i+1] == 'h' && s[i+2] == 'u') f = 1;
				i++;
			}
			if(!f)return "NO";
		}
		return "YES";
 	}
};

Medium
全探索余裕なので、全探索しましょう。貪欲法では解けないので、貪欲法を使った解法は撃墜しましょう。
追記:div1では全探索では解けないそうです。
追記2:全探索をしない場合は、最後の状態から考えて、前の状態に戻っていくDPで解けます。

class CasketOfStarEasy{
	int p[8],l,ans;
public:
	int f(const vector<int> &w2){
		vector<int> w(w2);
		int res = 0;
		for(int i = 0; i < l-2; i++){
			w[p[i]] = 0;
			int j1 = p[i];
			while(!w[--j1]);
			int j2 = p[i];
			while(!w[++j2]);
			res += w[j1]*w[j2];
		}
		//cout<<res<<endl;//デバッグ用
		return res;
	}
	int maxEnergy(vector <int> w) {
		l = w.size();ans=0;
		for(int i=0;i<l-2;i++){
			p[i]=i+1;
		}
		do{
			ans = max(f(w),ans);
		}while(next_permutation(p,p+l-2));
		return ans;
 	}
};

Hard
魔法少女をできる限り長生きさせようとしたときの、魔法少女の寿命を求める問題

238.02 + 300.54 + 0.00 = 538.56
Rating: 927->1002