SRM499_div2_Easy

プログラミング

先日参加したSRM499の問題の一つを再考してみる。

SimpleGuess（概要）

ある２つの自然数X,Yがあって、その和X+Yと差X-Yが
int型ベクタで与えられるヒント(vector hints)に含まれています。
そのような数X,Yはヒントに合致する限り幾つも考えられますが、
その中で積X×Yが最も大きいものの積X×Yを出力しなさい。

入力サイズ＆条件：
・2≦|hints|≦50（重複ナシ）
・1≦hints[i]≦100(∀i)
・hintsから最低でも一つは(X,Y)の組が考えられなければならない。
（例えばhints={1,8}はダメ）

例）・hints={1,4,9,2}
考えられるのは(X,Y)=(4,5),(1,3)の２組(順不同)。
積が最も大きいのは4×5=20
・hints = {4,99,8}
考えられるのは(X,Y)=(2,6)のみ。よって2×6=12

まあ、問題サイズが小さいので、

すべての(i,j)(i＞j)について
hints[i]とhints[j]の偶奇が等しいならば

X=(hints[i]+hints[j])/2
Y=|hints[i]-hints[j]|/2

が考えられるので、二重ループでコレを全探索するやり方が普通に通じます。
計算量はn=|hints|として

int getMaximum(vector <int> hints) {
	int X,Y,max=0;
	int siz;
	siz=hints.size();
	for(int i=0;i<siz;i++){
		for(int j=0;j<i;j++){
			if(((hints[i]+hints[j])%2)==0){
				X = abs(hints[i]-hints[j])/2;
				Y = abs(hints[i]+hints[j])/2;
				if(max<X*Y)max=X*Y;
			}
		}
	}
	return max;
}

あとは、X,Yの存在範囲がそもそも小さい（1≦X,Y≦98）ので、そっちを主軸に据えてもいい。
本番のコードを見ると意外とこっちも多かった。
計算量はn=|hints|,m=max{max_x,max_y}(本問では100)として（多分。不正確ですので注意）

int getMaximum(vector <int> hints) {
	int max=0;
	int siz;
	set<int> st;
	siz=hints.size();
	for(int i=0;i<siz;i++)st.insert(hints[i]);
	for(int x=98;x>0;x--){
		for(int y=x-1;y>0;y--){
			if(st.find(x+y)!=st.end() && st.find(x-y)!=st.end() && max<x*y){
				max=x*y;
			}
		}
	}
	return max;
}

ループの回数多いうえ、setでいちいち二部探索で検索しなきゃならないから、今回だとこっちのが遅い。


計算量を改善する方法としては、X*Yの値を大きくするには、X+Yをなるべく大きく、X-Yをなるべく小さくとればよいので、

「hintsに含まれる最大の偶数と最小の偶数」
「hintsに含まれる最大の奇数と最小の奇数」

から作られる(X,Y)のうちで最大のものが解となる。
計算量はn=|hints|として

int getMaximum(vector <int> hints) {
	int oddmax=-1,evenmax=-1,oddmin=200,evenmin=200;
	int oddxy,evenxy;
	int siz;
	siz=hints.size();
	for(int i=0;i<siz;i++){
		if(hints[i]%2){
			if(oddmax<hints[i])oddmax=hints[i];
			if(oddmin>hints[i])oddmin=hints[i];
		}else{
			if(evenmax<hints[i])evenmax=hints[i];
			if(evenmin>hints[i])evenmin=hints[i];
		}
	}
	if(oddmax>0 && oddmin<200)oddxy=(oddmax*oddmax-oddmin*oddmin)/4;else oddxy=-1;
	if(evenmax>0 && evenmin<200)evenxy=(evenmax*evenmax-evenmin*evenmin)/4;else 

evenxy=-1;
	return ((oddxy>evenxy)?oddxy:evenxy);
}

1重ループなので早い。しかし結局サイズが小さいこの問題でそこまで有利になるかどうかが疑問ですね。（きっちりこれで解が確実に得られることの証明考えないとChallengeされそうで怖いし）
コレ書くよりは安直に全探索をパパッと書き上げてSubmitして点数稼いだ方がいいような気がします。

だけど、終わった後に「こんな方法もあるな！」とか考えるのは楽しいですよね。



それではこの辺で（・ω・）ﾉｼ