AtCoder Beginner Contest 143 問題B 10/23 水
AtCoder Beginner Contest 143 問題B 10/23 水
2019/10/19(土)に実施されたコンテストに参加してみました。
それぞれの問題について、考察してみます。
たとえば、ABCのみっつのたこ焼きから2つを選ぶ方法は、次のような正方形で表現されます。
☓ABC
A◎◎◎
B◎◎◎
C◎◎◎
ただし、この問題では、同じたこ焼きを2つ選ぶことは認められていません。AA,BB,CCなどの対角線は除外します。また、左下の直角二等辺三角形と右上の直角二等辺三角形は、同じ組み合わせを表しているので、どちらか片方だけ考えればよいです。そして、問題文でも、
N(N-1)/2 と書いてあり、対角線を除いて、残りを半分にしてあります。
さて、個々の組み合わせを掛け算して総和は、「まず総和を求めてから掛け算をする」、「そこから対角線の総和を引き算する」、「最後に全体を2で割る」という方法で求めることができます。
これをプログラムにすると、次のようになります。
問題B 回答
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
cin >> N;
vector <int> d(N);
for (int i=0; i<N; i++) {
cin >> d.at(i);
}
int S1,S2,S3;
S1 = 0;
S2 = 0;
for (int i=0; i<N; i++) {
S1 = S1 + d.at(i);
S2 = S2 + (d.at(i))*(d.at(i));
}
S3 = (S1*S1 - S2) / 2;
cout << S3;
}