[Codeforces] Round #709 (Div. 2)

A번(AC) - Ad-hoc, Greedy

여러 상황에 대해서 최적의 해를 구해보면, 무조건 안에 들어있는 셀의 개수만큼의 벽을 지우면 된다는 것을 알 수 있다.

 

각 셀에 대해서 ㄱ자 모양으로 그리디하게 연결하면 무조건 바깥과 통하는 통로를 만들 수 있음을 알 수 있다.

전체 모양이 직사각형이고, 이는 ㄱ 모양들의 결합으로 볼 수 있기 때문에 반드시 이러한 접근 방법으로 풀 수 있다.

#include <bits/stdc++.h>
 
using namespace std;
 
int main(void){
    int t;
    cin >> t;
    for(int i = 0; i < t; i++){
        int a, b;
        cin >> a >> b;
        cout << a * b << "\n";
    }
    return 0;
}

B번(AC) - 수학

처음에 문제를 잘못읽고, 10^9개만큼의 정수가 들어오는 줄 알고 슬라이딩 윈도우로 처리하려다가

Break를 중간에 처리하는 과정에서 input값을 특정 케이스에서 덜 받는 문제가 발생해 오래 걸렸다.

 

처음에 문제만 보면, 수학이라서 쫄 수도 있기는 한데 차분히 모듈러 연산을 따라가면 된다.

 

문제를 요약하면 다음과 같다.

1. 문제에서 제시한 쿼리는 양수인 c를 등차로 가지는 등차수열을 m으로 나눈 모듈러 연산의 결과를 모아놓은 쿼리이다.

2. 이때, c가 m보다 작으므로 몫이 2만큼 거지는 상황은 발생하지 않는다. 따라서 공차가 더해짐에 따라서 결과는 2가지 경우만 존재하게 된다.

• 몫이 증가하는 경우 : 등차 수열 자체로만 보면 이전 값을 x라 했을 때 x + c인데, 몫이 증가하는 경우이므로 x + c - m이 된다.           이때 c < m 이므로 이전 수인 x보다 무조건 작다.
• 몫이 같은 경우 : 이 경우는 x + c이므로 이전 수인 x보다 크거나 같다.(같은 경우는 c가 0인 경우)

즉, 들어오는 값들을 순차적으로 바라보면서

이전 값보다 큰 경우는 1번 케이스, 반대의 경우는 2번 케이스이다.

 

1번 케이스의 결과를 a[i - 1] - a[i] (1<=i < n)이라 할 때 m - c이다.

2번 케이스의 결과를 a[i] - a[i.- 1] (1<=i < n)이라 할 때 c이다.

 

만약 2개 중 단 하나라도 해당하는 값이 2개 이상이면 inconsistent로써 -1을 출력해주면 된다.

그렇지 않은 경우 중

1) 1번이나 2번 케이스가 undefined인 경우(monotonically increaing/decreasing function일 때 이러한 상황이 발생한다.) m이 가질 수 있는 값은 무한대이므로 0을 출력해주면된다.

>> 잘 생각해보면 m - c는 결정되었는데 c가 결정되지 않았다는 것의 의미는 엄청 큰 c를 잡고 차이가 m - c만큼의 m을 잡으면 무방하므로 매우 큰 m을 가져도 된다. 반대로 c가 결정되었는데 m - c가 미정인 경우에는 c를 고정시켜놓고 차이가 무한대일 수 있으므로 매우 큰 m을 가져도 된다.

 

2) 둘 다 defined인 경우는 주어진 쿼리에 있는 최댓값을 m이 넘기만 하면 된다.

즉, 1번 결과를 통해 구해지는 값이 m - c, 2번 결과를 통해 구해지는 값이 c이므로 2개의 결과를 더한 값이 주어진 쿼리에 존재하는 최댓값을 넘기면 된다.

 

만약 넘기지 못하면 inconsistent이므로 -1을 출력해주면 된다.

넘기는 경우는 m, c를 순차적으로 출력해주면 된다.

(기본적으로 이 케이스는 공차가 0인 경우 예외케이스가 발생해서 진행해주는 것이다.)

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
typedef long long ll;

int main(void){
    fastio;
    ll t;
    cin >> t;

    for(int i = 0; i < t; i++){
        ll n;
        ll max_value = -1;
        cin >> n;
        vector<ll> data;
        if(n == 1){
            cout << 0 << "\n";
            int trash;
            for(int i = 0; i < n; i++){
                cin >> trash;
            }
            continue;
        }
        else{
            for(int i = 0; i < n; i++){
                int temp;
                cin >> temp;
                if(temp > max_value){
                    max_value = temp;
                }
                data.push_back(temp);
            }

        }
        
        ll c = -1;
        ll pq = -1;
        ll front = data[0];
        ll back = data[1];

        if(back >= front){
            c = back - front;
        }
        else{
            pq = front - back;
        }
        
        bool error = false;
        for(int i = 2; i < n; i++){
            front = back;
            back = data[i];
            if(back >= front){
                if(c == -1){
                    c = back - front;
                }
                else{
                    if(c != back - front){
                        cout << -1 << "\n";
                        error = true;
                        break;
                    }
                }
            }
            else{
                if(pq == -1){
                    pq = front - back;
                }
                else{
                    if(pq != front - back){
                        error = true;
                        cout << -1 << "\n";
                        break;
                    }
                }
            }
        }

        if(error) continue;
        if(c == -1){
            cout << 0 << "\n"; // if m - c가 유니크하면
        }
        // c는 unique하게 결정된 상황
        else{
            if(pq == -1){
                cout << 0 << "\n";
            }
            else{
                if(c + pq > max_value){
                    cout << c + pq << " "<< c << "\n";
                }
                else cout << -1 << "\n";
                
            }         
        }
    }
    return 0;
}

업데이트 예정

---------------------------------------

C번