TopCoder SRM 764 : Combined Medium FourSquareSum

Registerし忘れて不参加だったのだけど、これだとどうでもいいやという気になる問題だった。
https://community.topcoder.com/stat?c=problem_statement&pm=15684&rd=17663

問題

非負整数の４つ組a,b,c,dが与えられる。
これらの2乗和は偶数で、a^2+b^2+c^2+d^2=2nと表せるとする。
別の非負整数の４つ組s,x,y,zで、s^2+x^2+y^2+z^2=nと表せるものを構築せよ。

解法

nではなくa,b,c,dがわざわざ与えられているので、これらを使うことを考える。
(s+x)^2+(s-x)^2+(y+z)^2+(y-z)^2 = 2*(s^2+x^2+y^2+z^2) = a^2+b^2+c^2+d^2
なので、aとb、cとdの偶奇が同じでかつa≧b、c≧dになるようa,b,c,dを並べ替えれば

• s+x=a
• s-x=b
• y+z=c
• y-z=d

となるs,x,y,zは容易に求められる。

class FourSquareSum {
	public:
	vector <int> DivideByTwo(int a, int b, int c, int d) {
		vector<int> V={a,b,c,d};
		sort(ALL(V));
		do {
			if(V[0]%2==V[1]%2 && V[2]%2==V[3]%2) {
				int s=(V[0]+V[1])/2;
				int x=max(V[0],V[1])-s;
				int y=(V[2]+V[3])/2;
				int z=max(V[2],V[3])-y;
				return {s,x,y,z};
				
			}
			
		} while(next_permutation(ALL(V)));
		return {};
	}
}

まとめ

面白いけどコンピュータでやる意味あるのかな。