Problem


Key Idea

  • ๊ฐ university ๋ณ„๋กœ ๋”ฐ๋กœ ๊ณ„์‚ฐ์ด ๊ฐ€๋Šฅํ•˜๋‹ค.
  • ํ•œ university์— ํ•™์ƒ ์ˆ˜๊ฐ€ \(sz\) ๋ผ๋ฉด, \(1 \le k \le sz\) ์ธ k๊ฐ’์—๋งŒ ์˜ํ–ฅ์ด ์žˆ๋‹ค.


์ฒซ ๋ฒˆ์งธ ์˜ˆ์‹œ.

7
1 2 1 2 1 2 1
6 8 3 1 5 1 5


๊ฐ university ๋ณ„๋กœ list์— ๋‹ด๊ณ , sortingํ•˜๋ฉด

univ[1]: 3 5 5 6
univ[2]: 1 1 8


\(univ[1]\) ๊ณ„์‚ฐ: \(k = 3\) ์ผ๋•Œ 6์ด ์ œ์™ธ๋˜๋ฉด์„œ, \(ans[3]\)์—๋งŒ 6์ด ๋น ์ง„๋‹ค.

ans: 0 19 19 13 19 0 0 0

์ฆ‰, \(sz \mod k\) ๊ฐœ ๋งŒํผ ์•ž์—์„œ๋ถ€ํ„ฐ(์ž‘์€๊ฒƒ๋ถ€ํ„ฐ) ๋น ์ง„๋‹ค.


  1. university๋ณ„๋กœ sort.
  2. \(univ[i] (1 \le i \le n)\) ๋ฐฐ์—ด์„ ๋ˆ„์ ํ•ฉ ๋ฐฐ์—ด๋กœ ๋ณ€ํ™˜
  3. \(univ\) ๋ฐฐ์—ด์„ ์ˆœํšŒํ•˜๋ฉด์„œ, ๊ฐ \(k\)๊ฐ’ \((1 \le k \le sz)\)์— ๋Œ€ํ•ด \((์ดํ•ฉ - univ[i][sz\%k-1])\) ์„ \(ans[k]\)์— ๋”ํ•ด์ค€๋‹ค.


  • Time: \(O(n{\log}n)\)


Implementation

/**
 * author: jooncco
 * written: 2021. 5. 8. Sat. 00:22:56 [UTC+9]
 **/

#include <bits/stdc++.h>
using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
typedef vector<ll> vl;

int t,n;
ll u[200010], s;

int main() {

    FAST_IO;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i=0; i < n; ++i) cin >> u[i];
        vector<vl> univ(n+1,vl());
        ll ans[200010]= {0};
        for (int i=0; i < n; ++i) {
            cin >> s;
            univ[u[i]].push_back(s);
        }
        for (int i=1; i <= n; ++i) {
            int sz= univ[i].size();
            if (sz) {
                sort(univ[i].begin(),univ[i].end());
                for (int j=1; j < sz; ++j) univ[i][j] += univ[i][j-1];
                for (int k=1; k <= sz; ++k) {
                    ans[k] += univ[i][sz-1];
                    if (sz%k > 0) ans[k] -= univ[i][sz%k-1];
                }
            }
        }
        for (int i=1; i <= n; ++i) {
            if (i > 1) cout << " ";
            cout << ans[i];
        }
        cout << "\n";
    }
}

Tags:

Updated:

Leave a comment