[Codeforces] Codeforces Round #418 이야기

A, B, C번 문제까지 봤지만 오늘은 B번 문제를 틀리게 되어 A번 문제 1문제만 맞히게 되었다.

최종적으로 1290(+10)으로 마무리하게 되었는데 왜 10점이 오른지도 잘 모르겠다.

A. An abandoned sentiment from past :: http://codeforces.com/contest/814/problem/A

0이 있는 위치에 3번째 라인에 주어진 수를 넣어 최종적 A 배열이 오름차순이 안되도록 하면 된다.

결국 이건 B를 내림차순으로 정렬해서 A 배열에 넣을 때 A 배열이 오름차순이 되는지 확인하면 되는지 물어보는 문제이다.

시간 복잡도는 O(n) 이다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool comp(const int &a, const int &b)
{
    return a > b;
}
int main()
{
    int n, m;
    int a[202];
    int b[202];
 
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for (int i = 0; i < m; i++)
        scanf("%d", &b[i]);
 
    sort(b, b + m, comp);
 
    int j = 0;
    for (int i = 0; i < n; i++)
        if (a[i] == 0)
        {
            a[i] = b[j];
            j++;
        }
 
    bool chk = true;
    for (int i = 1; i < n; i++)
        if (a[i] <= a[i - 1])
            chk = false;
 
    if (chk)
        printf("No");
    else
        printf("Yes");
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

B. An express train to reveries :: http://codeforces.com/contest/814/problem/B

솔직히 이 문제는 틀리면 안되는 문제였다.

쉬운 문제에 속하는 것인데 왜 시간이 촉박해지면 문제를 접근하는데 허둥지둥 하는지 모르겠다.

이 문제는 A 배열과 B 배열이 C 배열과 모든 수가 일치하되 2개만 다르게 만들 수 있는 C 배열을 만들면 되는 문제이다.

애초에 A, B에서 서로 다른 수의 개수를 구분해내면 서로 다른 수가 2개 아니면 1개임을 알 수 있다.

이 방식을 이용해서 문제를 접근하였는데 

테스트 #22인

4
3 2 1 3
4 2 1 2

에서 틀린것을 보니 실수가 있었는게 맞는 것 같다.(어떠한 처리 하나가 부족했는 듯 하다.)

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int a[1002], b[1002], c[1002];
bool chk[1002];
 
int main()
{
    int n;
 
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for (int i = 0; i < n; i++)
        scanf("%d", &b[i]);
 
    vector<int> vc;
    for (int i = 0; i < n; i++)
    {
        if (a[i] != b[i])
            vc.push_back(i);
        else
        {
            c[i] = a[i];
            chk[a[i]] = true;
        }
    }
 
 
    vector<int> get;
    for (int i = 1; i <= n; i++)
        if (!chk[i])
            get.push_back(i);
 
    int len = get.size();
 
    int cntA = 0, cntB = 0;
 
 
    pair<int, int> p[5];
 
    if (get.size() == 2)
    {
        p[0] = { get[0], get[1] };
        p[1] = { get[1], get[0] };
 
        c[vc[0]] = get[0];
        c[vc[1]] = get[1];
 
        for (int i = 0; i < n; i++)
        {
            if (a[i] == b[i] && b[i] == c[i])
                continue;
            else if (a[i] != c[i])
                cntA++;
            else if (b[i] != c[i])
                cntB++;
        }
 
        if (!(cntA == 1 && cntB == 1))
        {
            cntA = 0, cntB = 0;
            c[vc[1]] = get[0];
            c[vc[0]] = get[1];
 
            for (int i = 0; i < n; i++)
            {
                if (a[i] == b[i] && b[i] == c[i])
                    continue;
                else if (a[i] != c[i])
                    cntA++;
                else if (b[i] != c[i])
                    cntB++;
            }
        }
 
 
    }
 
    else if (get.size() == 1)
    {
        p[0] = { get[0], -1 };
        c[vc[0]] = get[0];
 
        for (int i = 0; i < n; i++)
        {
            if (a[i] == b[i] && b[i] == c[i])
                continue;
            else if (a[i] != c[i])
                cntA++;
            else if (b[i] != c[i])
                cntB++;
        }
 
 
    }
    for (int i = 0; i < n; i++)
        printf("%d ", c[i]);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>