Codeforces #1497B M-arrays

문제

https://codeforces.com/problemset/problem/1497/B

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        int n, m;
        cin >> n >> m;
        vector<int> a(m, 0);
        int tmp;
        for(int i = 0; i < n; i++){
            cin >> tmp;
            a[tmp%m]++;
        }
        int mid = (m+1)/2;
        int ans = 0;
        for(int i = 1; i < mid; i++){
            int mi = min(a[i], a[m-i]);
            if(mi == 0){
                ans += a[i] + a[m-i];
            }
            else{
                ans++;
                a[i] -= mi+1;
                a[m-i] -= mi+1;
                if(a[i] > 0) ans += a[i];
                if(a[m-i] > 0) ans += a[m-i];
            }
            a[i] = a[m-i] = 0;
        }
        if(a[0] > 0) ans++;
        if(mid < m && a[mid] > 0) ans++;
        cout << ans << "\n";
    }
    return 0;
}

배열 a 를 모든 인접한 원소의 합이 m 으로 나눠질 수 있는 배열들로 나누려고 할 때, 배열의 최소 개수를 구하는 문제이다.

인접한 원소를 각각 a, b 라고 했을 때 a+b (mod m) 를 a (mod m) + b (mod m) 로 나타내면 a, b 를 m 으로 나눈 나머지의 합이 m 일 경우 나누어 떨어진다고 볼 수 있다.

나머지가 0, (m+1)/2 인 경우는 나머지가 같은 숫자들끼리 묶을 수 있다. 그 밖의 나머지들은 나머지의 합이 m 인 값끼리 묶을 수 있는데 최대 공통으로 가지고 있는 개수 * 2 + 1 개 까지 가능하다. (예 - m 이 8 일 때, 1 7 1 7 1 or 7 1 7 1 7) 이 때 나머지의 합이 m 이 되지 못하는 원소들은 자신 하나로 구성된 배열이 되어야 하므로 남은 개수만큼 결과값에 더해주어야 한다.

모든 a 배열의 원소 % m 값의 개수를 저장하고 굵게 표시한 부분에 유의하면서 구현하면 된다.