Codeforces Round #631 (Div. 2) 다시 돌아온 블루

Codeforces Round #631 (Div. 2)

짜잔 내가 돌아왔다!

Qualification Round 2020

코드잼도 하고옴

https://codeforces.com/contest/1330

Dashboard - Codeforces Round #631 (Div. 2) - Thanks, Denis aramis Shitov! - Codeforces

A. Dreamoon and Ranking Collection

지금까지 내가 한등수를 입력 받는다. 그리고 몇번 더 대회에 참가할건지 입력 받는다. 1등부터 n등까지 모두 하고 싶을때 만족할 수 있는 n의 최대값 찾는 문제이다. 

범위가 100이니 완탐 때리면 된다! 해석이 제일 어려웠던 문제

int arr[MAXN];
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int T;
    cin >> T;
    while (T--) {
        int n,x;
        cin >> n >> x;
        for (int i = 0; i <= 205; i++) {
            arr[i] = 0;
        }
        for (int i = 1; i <= n; i++) {
            int tem;
            cin >> tem;
            arr[tem] = 1;
        }
        for (int i = 1; i <= 205; i++) {
            if (x == 0 && arr[i] == 0) {
                cout << i - 1 << "\n";
                break;
            }
            if(arr[i]==0){
                x--;
            }
        }
    }
}

 

B. Dreamoon Likes Permutations

 

입력받은 수 배열을 배열1 과 배열 2로 떨어트리려고 한다. 배엷1과 배열 2는 각각 1~n까지 숫자들을 하나씩 포함해야한다. 

 

처음 배열을 쭉 보면서 각수의 갯수를 che배열에 기록하고 che배열을 다시 쭉 보면서 가능한지 체크한다. 

갯수가 2 2 2 2 2 2 1 1 1 1 1 0 0 0이런식이여야지 2 2 2 1 1 2 2 2 1 11 1 1 or 2 2 2 2 1 1 1 0 1 1 1 1 0 0 이런식이면 안된다.

그뒤 앞뒤에서부터 보면서 쪼개준다 끝!

int arr[MAXN];
int crr[MAXN];
bool c2[MAXN];
bool c3[MAXN];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> arr[i];
            crr[i] = 0;
            c2[i]=c3[i]=0;
        }
        for (int i = 1; i <= n; i++) {
            crr[arr[i]]++;
        }
    
        int che = 0;
        int left=0;
        int an = 0;
        for (int i = 1; i <= n; i++) {
            if (crr[i] != 2) {
                an = i - 1;
                left = i;
                break;
            }
        }
        if (left == 1)
            che = 1;
        int an2 = 0;
        for (int i = left; i <= n ; i++) {
            if (crr[i] == 2) {
                che=1;
                break;
            }
            else if (crr[i] == 0) {
                left = i;
                an2 = i - 1;
                break;
            }
        }
        for (int i = left; i <= n ; i++) {
            if (crr[i]) {
                che = 1;
                break;
            }
        }
        if (che) {
            cout << 0 << '\n';
            continue;
        }
        int cf = 0;
        vector<pii> v;
        int a1 = an, a2 = an2;
        if (a1 + a2 != n) {
            cout << 0 << '\n';
            continue;
        }
        left = 0;
        int midche = 0;
        for (int i = 1; i <= a1; i++) {
            if (c2[arr[i]] == 0) {
                c2[arr[i]] = 1;
            }
            else {
                midche = 1;
            }
        }
        for (int i = a1+1; i <= n; i++) {
            if (c3[arr[i]] == 0) {
                c3[arr[i]] = 1;
            }
            else {
                midche = 1;
            }
        }
        if (midche == 0) {
            v.push_back({ a1, a2 });
        }
 
        for (int i = 1; i <= a1; i++) {
            c2[arr[i]] = 0;
        }
        for (int i = a1 + 1; i <= n; i++) {
            c3[arr[i]] = 0;
        }
        midche = 0;
        if (a1 == a2)
            midche = 1;
        for (int i = 1; i <= a2; i++) {
            if (c2[arr[i]] == 0) {
                c2[arr[i]] = 1;
            }
            else {
                midche = 1;
            }
        }
        for (int i = a2 + 1; i <= n; i++) {
            if (c3[arr[i]] == 0) {
                c3[arr[i]] = 1;
            }
            else {
                midche = 1;
            }
        }
        if (midche == 0) {
            v.push_back({ a2, a1 });
        }
        if (v.size() == 0) {
            cout << 0 << '\n';
            continue;
        }
 
        cout << v.size()<<'\n';
        for (int i = 0; i < v.size(); i++) {
            cout << v[i].first << ' ' << v[i].second << '\n';
        }
    }
}

 

C. Dreamoon Likes Coloring

 

문제가 읽어보면 범위가 아주 욕나오게 복잡하지만 잘보면 그냥 각 색을 l1,l2,,,,lm의 길이만큼 칠할수 있는곳에 칠하겠다는 거다. 

T1은 결국 3칸칠하고 2칸칠하고 2칸 칠한다는뜻

1)모든칸을 중복 없이 칠했을때의 길이가 전체 길이보다 짧으면 탈락(12줄)

2)1번색은 1칸 2번색은 2칸부터 칠할때 즉 최소로 칠할때 전체길이보다 길면 탈락(16줄)

3) 1과 2를 만족하므로 2의 gap만큼 중간에 띄워주면 완성! 25줄 

최소 한번씩은 칠해줘야함

주의할점 ! n번색을 n칸부터 칠할때 마지막 칠할점이 n보다 크면 안됨! 이거때문에 3번틀림 개가튼..

 

ll arr[MAXN];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, m;
    cin >> n >> m;
    ll snum = 0;
    for (int i = 1; i <= m; i++) {//l칸씩 칠 하겠다.
        cin >> arr[i];
        snum += arr[i];
   }
    if (snum < n) {
        cout << -1;
        return 0;
    }
    if (m - 1 + arr[m] > n) {
        cout << -1;
        return 0;
    }
    ll gap = n - (m - 1 + arr[m]);
    int whi = n-arr[m]+1;
    vector<int> v;
    v.push_back(whi);
    int che = 0;
    for (int i = m-1; i >= 1; i--) {
        whi--;
        if (gap >= arr[i] - 1) {
            gap -= arr[i] - 1;
            whi -= arr[i] - 1;
        }else if (gap < arr[i] - 1) {
            whi -= gap;
            gap = 0;
        }
        if (whi + arr[i] - 1 > n)
            che = 1;
        v.push_back(whi);
    }
    if (che) {
        cout << -1;
        return 0;
    }
    for (int i = m-1; i >= 0; i--)
        cout << v[i] << ' ';
}