SRM499 Div2

久々にpracticeしました。

Easy 229.95/250
正の整数が沢山あって、X+YとX-Yが含まれている。X*Yの最大値を求めよ。

全探索で良い。AとB(A>B)の偶奇が一致するとき、整数X,Yは存在して、X=(A+B)/2,Y=(A-B)/2となる。
加法定理を逆向きに使うときにこんな感じの考え方をするので、240点代で解けなかったのは残念です。

class SimpleGuess{
public:
	int getMaximum(vector <int> s) {
		int len = s.size(),res = 0;
		for(int i = 0; i < len; i++){
			for(int j = 0; j < len; j++){
				if(i!=j && !((s[i]+s[j])%2)){
					res = max(res,abs(s[i]-s[j])*(s[i]+s[j])/4);
				}
			}
		}
		
		return res;
 	}
};

Medium 434.98/500
あるウサギXと同じ色でX以外のウサギの羽数が与えられている。ウサギは最低何羽いるか。

Yというデータが与えられていれば、ある色のウサギが(Y+1)羽存在することが分かる。(Y+1)羽以上存在する場合は、別な色になるので、色が何種類になるか考えればよい。

class ColorfulRabbits{
public:
	int getMinimum(vector <int> s) {
		sort(s.begin(),s.end());
		int len = s.size(),res = 0;
		
		for(int i = 0; i < len; i++){
			int a = s[i],b = 1,c = 0;
			while(i < len && a == s[i]){
				c++;
				if(c == s[i]+2){
					b++;
					c = 1;
				}
				i++;
			}
			i--;
			res += (a+1)*b;
		}
		
		return res;
 	}
};

Hard -/950
表に文字列、裏に数字が書いてあるカード(文字列の長さは全て等しい)を並べて、回文を作り、数字の和が最大になるようにする。

ある文字列とそれの逆になっている文字列で、数字が大きくなるようにペアを作って、回文になっている文字列の中で、一番数字が大きいものを真ん中に入れるだけ。

これは解けなきゃいけない気がするが解けてない。