Codeforces #1409C Yet Another Array Restoration

문제

https://codeforces.com/problemset/problem/1409/C

걸린 시간

02 : 07 : 54

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
using namespace std;

int n, x, y;
vector<int> A, result;
set<int> a;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        cin >> n >> x >> y;
        int minA = INF;
        for(int i = 1; i <= 50; i++){
            for(int j = 1; j <= 50; j++){
                A.clear();
                a.clear();
                a.insert(x); a.insert(y);
                int inc = j;
                while(a.size() != n){
                    a.insert(inc);
                    inc += i;
                }
                for(auto it = a.begin(); it != a.end(); it++)
                    A.push_back(*it);
                // 인접한 원소간의 차이가 모두 같은지 검사
                bool diff = true;
                int last = A[1]-A[0];
                for(int k = 2; k < n; k++)
                    if(last != A[k]-A[k-1])
                        diff = false;
                if(!diff) continue;
                // 가장 작은 배열 A의 최대값을 갱신
                int maxA = A[n-1];
                if(minA > maxA){
                    minA = maxA;
                    result = A;
                }
            }
        }
        for(int i = 0; i < result.size(); i++)
            cout << result[i] << " ";
        cout << "\n";
    }
    return 0;
}

몇 가지 예제들을 손으로 직접 풀어보면서 약수와 관련된 규칙이 있는 것 같아 이를 구현했지만 예로 주어진 테스트케이스만 정상적으로 돌아갈 뿐, 모든 경우에 대해 올바른 답을 출력하지 못했다. 그래도 알고리즘엔 문제가 없어 보여 여러 가지 반례를 확인하다 보니 모든 경우를 시도하도록 하면 해결할 수 있을 것 같아 수정했고, 1초 안으로 아슬아슬하게 통과했다.

문제의 채점 방식이 조금 특이했는데 출력값을 그대로 비교하는 것이 아닌 문제의 조건에 맞는 추가적인 연산을 한 번 더 진행한다. 분명 출력 순서는 상관이 없다고 설명되어 있지만 이런 채점 방식을 처음 접해보았기 때문에 예제 출력과 순서가 달라도 과연 올바르게 채점이 될 까 의심했었다.