[Codeforces] Codeforces Round #441 이야기

요즘 코포에 대해 따로 글을 올리지 않긴했는데, 늘 코드포스를 하고 있긴 하다..

오늘은 문제 지문을 잘못 이해한 것을 다시 되돌아보기 위해 글을 하나 올리고자 한다.

B. Divisiblity of Differences :: http://codeforces.com/contest/876/problem/B

You are given a multiset of n integers. You should select exactly k of them in a such way that the difference between any two of them is divisible by m, or tell that it is impossible.

당신은 n개의 수를 받게 됩니다. 정확히 k개를 선택해야하는데 두개의 차가 m으로 나눌 때 나머지가 같은 것들을 찾아야합니다.

이제 이 문제를 풀기위해 모듈러 연산에 대해 생각을 해보자.

우리는 위의 문제에서 (a - b) % mod = t인 a,b 집합을 구해야한다.

이때 모듈러 특성을 이용하면 (a - b) % mod = (a % mod - b % mod) % mod임은 자명하다.

그렇다면 우린 (a-b) % mod = 0인 a,b 집합에 대해 생각 해 볼 수 있다.

그렇게 된다면 ( a % mod - b % mod ) % mod = 0이되고, 결국 a % mod = b % mod라는 값을 도출 할 수 있다.

따라서 우리는 입력으로 받는 각 수를 mod로 나눈 나머지 값이 같은 집합들을 찾아내주면 된다.

이때 찾아내줄때 mod로 나눈 나머지가 같은 수가 k개가 되면 정답을 출력하고 종료한다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
int arr[100002];
vector<int> vc[100002];
 
int main()
{
    int n, k, mod;
    scanf("%d %d %d", &n, &k, &mod);
 
    for (int i = 0; i < n; i++)
    {
        int val;
        scanf("%d", &val);
 
        vc[val % mod].push_back(val);
 
        if (vc[val % mod].size() == k)
        {
            printf("Yes\n");
            for (auto i : vc[val % mod])
                printf("%d ", i);
            
                return 0;
        }
    }
    printf("No");
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>