Codeforces #1484B Restore Modulo

문제

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

걸린 시간

- 실패

풀이

C++

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int n;
        cin >> n;
        vector<int> a(n);
        for(auto& i : a) cin >> i;
        // c == 0
        bool equal = true;
        bool seq = false;
        for(int i = 1; i < n; i++){
            if(a[i-1] == a[i]) seq = true;
            else equal = false;
        }
        if(equal){
            cout << 0 << "\n";
            continue;
        }
        if(seq){
            cout << -1 << "\n";
            continue;
        }
        // c != 0
        set<int> s;
        for(int i = 1; i < n; i++){
            s.insert(a[i]-a[i-1]);
        }
        if(s.size() == 1){
            cout << 0 << "\n";
            continue;
        }
        if(s.size() > 2){
            cout << -1 << "\n";
            continue;
        }
        int c = *s.rbegin();
        int m = c + -*s.begin();
        bool more = false;
        for(int i = 0; i < n; i++){
            if(a[i] >= m){
                more = true;
            }
        }
        if(more){
            cout << -1 << "\n";
            continue;
        }
        cout << m << " " << c << "\n";
    }
    return 0;
}

문제는 c == 0 일 때와 c != 0 일 때로 구분할 수 있다.

s % m = a[0] (i == 0)
(a[i-1]+c) % m = a[i] (1 <= i < n)

c == 0 일 땐 모든 a[i] 값이 같아져야 한다. 모든 값이 같다면 무수히 많은 m 값이 존재하므로 0 을 출력, 일부만 연속적으로 같은 값이 존재한다면 c == 0 에 모순이므로 -1 을 출력한다.

두 경우를 제외하면 모든 값이 서로 다른 경우가 남게된다. (c != 0)

c, m 값은 c < m 조건과 모든 a[i] 값이 (mod m) 에 의한 결과값이므로 m 보다 작다는 조건으로부터 찾을 수 있다.

두 가지 조건에 의해 a[i-1]+c 값은 0 부터 최대 2(m-1) 값을 갖게되므로, m 보다 작을 경우는 a[i-1]+c, 크거나 같은 경우는 a[i-1]+c-m 로 한정된다.

(a[i-1]+c) % m = a[i] 식을 a[i-1]+c = a[i], a[i-1]+c-m = a[i] 로 표현할 수 있고 a[i]-a[i-1] 에 대해 정리하면 a[i]-a[i-1] = c or c-m 임을 알 수 있다. 요약하면 a[i]-a[i-1] 는 c 또는 c-m 두 가지 값만으로 표현될 수 있다는 것을 의미한다.

c-m 은 c < m 조건에 의해 항상 음수이다. 만약 양수, 음수 둘 중 값이 하나만 나올 경우 무수히 많은 m 값이 존재할 수 있으므로 0 을 출력하고 양수, 음수의 값이 각각 하나씩이 아니라면 -1 을 출력한다.

마지막으로 (mod m) 처리한 값 a[i] 가 m 보다 크거나 같을 경우 -1 을, 그렇지 않으면 구한 m 과 c 를 출력하면 된다.

수학문제는 조건과 규칙(굵게 처리한 부분)으로부터 가능한 모든 경우를 꼼꼼히 파악하는게 정말 어려운 것 같다. 풀이를 보고도 이해하기 힘들었다.