← 전체 글로 돌아가기
competitive-programming2021년 5월 8일1분 분량

[Codeforces] 1519C. Berland Regional 풀이

수정일: 2021년 5월 8일

Math
지원 언어:enko

#Problem

1519C. Berland Regional

#Approach

  • 각 university 별로 따로 계산이 가능하다.
  • 한 university에 학생 수가 szsz 라면, 1≤k≤sz1 \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]univ[1] 계산: k=3k = 3 일때 6이 제외되면서, ans[3]ans[3]에만 6이 빠진다.

ans: 0 19 19 13 19 0 0 0

즉, ** szmod  ksz \mod k 개 만큼 앞에서부터(작은것부터) 빠진다.

  1. university별로 sort.
  2. univ[i](1≤i≤n)univ[i] (1 \le i \le n) 배열을 누적합 배열로 변환
  3. univuniv 배열을 순회하면서, 각 kk값 (1≤k≤sz)(1 \le k \le sz)에 대해 (총합−univ[i][sz%k−1])(총합 - univ[i][sz\%k-1]) 을 ans[k]ans[k]에 더해준다.

#Code

/**
 * 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";
    }
}

#Complexity

  • Time: O(nlog⁡n)O(n{\log}n)
  • Space: O(n)O(n)