Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

A. Reorder (Codeforces Round #678 Div. 2)

Codeforces こどふぉ competitive programming c++

この問題に1時間かけてしまったばっかりに、青から水に落ちました・・・。

問題

https://codeforces.com/contest/1436/problem/A

問題概要

整数が含まれる長さnの配列aと、別に整数mが与えられる。

配列aの中身を任意に並べ替えることで

\sum_{i=1}^n \sum_{j=i}^n \frac{a_j}{j}

が、mと等しくなるようにできるかどうかを判定せよ。ただし、除算結果に対して丸めは発生しないものとする。

考察

シグマを展開しますと、以下のようになります。

(\frac{a_1}{1} + \frac{a_2}{2} + \frac{a_3}{3} + ... + \frac{a_n}{n}) + (\frac{a_2}{2} + \frac{a_3}{3} + ... + \frac{a_n}{n}) + (\frac{a_3}{3} + ... + \frac{a_n}{n}) + ... + (\frac{a_n}{n})

\frac{a_1}{1}は一度しか現れないので、\frac{a_1}{1}つまりa_1です。

\frac{a_2}{2}は二度現れるので、\frac{a_2}{2} \times 2つまりa_2です。

\frac{a_3}{3}は三度現れるので、\frac{a_3}{3} \times 3つまりa_3です。

...

\frac{a_n}{n}はn度現れるので、\frac{a_n}{n} \times nつまりa_nです。

ようするに、配列aがどのように並んでいるかは全く関係なく、計算結果は\sum_{i=1}^n a_iになります。

よってこの問題は、配列aの要素の和とmが等しいか否か、という問題と同じことなのでした。

#include <bits/stdc++.h>
using namespace std;
 
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define REP(i, n) FOR(i, 0, (n))
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        int a;
        int sum = 0;
        REP(i, n) {
            cin >> a;
            sum += a;
        }
        cout << (sum == m ? "YES" : "NO") << endl;
    }
    return 0;
}

感想

こんな簡単な算数に1時間かける青コーダー、おる？