[白俊]14929:面倒(SIB)

質問リンク

https://www.acmicpc.net/problem/14929

方法/解答

問題をよく読んでみると,n個の値があり,nC 2で可能なすべての2個の値の積を見つけた.
すなわち,a,b,c,da,b,c,dと入力すると,ab+ac+ad+bc+bd+ac+bc+bd+cdab+ac+ad+bd+bd+cdab+ac+ad+bc+bd+cdとなる.
この問題を解決するために,2つの数の積で解決することにした.
入力したすべての値を加算し、平方にします.
(a,b,c,d)∗(a,b,c,d)=a2+b2+c2+d2+2ab+2ac+2ad+2bc+2bd+2cd(a, b, c, d) * (a, b, c, d) = a^2 + b^2 + c^2 + d^2 + 2ab + 2ac + 2ad + 2bc + 2bd + 2cd(a,b,c,d)∗(a,b,c,d)=a2+b2+c2+d2+2ab+2ac+2ad+2bc+2bd+2cd
前述したように、この過程で、2∮(ab+ac+ad+bc+bd+cd)2*(ab+ac+ad+bd+cd)2∮(ab+ac+ad+bd+cd)の答えを求める形式が得られる.
そのため、問題の解決と救済
1.すべての入力値の合計
2.すべての入力値の二乗和
そして,(1)の二乗で(2)を減算し,さらに2で割ると正解が得られる.
このような方法が見つかった以上、問題で考えなければならないのはオーバーフローだけだ.
個数が10万以下なので、値段は100以下です.
値の合計は-1000000～1000000です.
値の2乗和は、0～10000000の間の値です.intインチ、
値の合計の2乗を使用するため、値の合計を格納する変数はlong longとして宣言されます.

解答コードリンク(Github)

Solution Github Link

解答コード(C++)

#include <iostream>

using namespace std;

void	fastio(void);

int main(void)
{
    int	num;
	int	tmp;
    int	square_num = 0;
    long long	add_num = 0;   

	fastio();
    cin >> num;
	for (int i = 0; i < num; i++)
	{
		cin >> tmp;
		square_num += tmp * tmp;
		add_num += tmp;
	}
	add_num *= add_num;
	add_num -= square_num;
	cout << add_num/2 << "\n";
	return (0);
}

void	fastio(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}