코드포스 - Educational Codeforces 49 Round

오랜만에 에듀코포가 있어 해보게 되었다.

너무 오랜만이라 그런지 문제를 해석해야하는데 해석도 안되고 문제를 읽기도 싫어서 대충 예제를 보고 풀려고 했지만 A번은 1시간 동안 안 풀려서 

B -> A -> C로 풀었더니 1시간이 훌쩍 지나가버렸다.

A번은 두 문자의 차이가 2 또는 0(같은것)인것을 보면 되는 단순한 문제였는데 문제를 안읽어 제출을 많이 했다.

B번은 대충 배열 쓰면 되겠지하고 봤더니 n의 범위가 최대 10^9여서 멍 때리다가 규칙을 찾고 대충 제출 했지만 케이스 n == 2일때만 틀려서 2일땐 그냥 노가다로 if문 떡칠을 하였다.

C번은 처음에 O(n^2)로 풀었는데 TLE가 떠서 O(n) 풀이가 있을꺼 같아 살짝 그리디하게 짜봤더니 AC가 떳다.

시간 복잡도 

A번 -> O(N)

B번 -> O(1) 

C번 -> O(N)

D는 한번 풀어보고 싶었지만 SoC Robot 대회 준비를 해야되서 나중에 풀어보기로 했다.

A번 Palindromic Twist

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
 
using namespace std;
 
typedef long long ll;
typedef unsigned char BYTE;
typedef unsigned int UI;
typedef unsigned short US;
typedef unsigned long long ULL;
 
vector<vector<pair<int, int>>> map;
vector<int> ans;
queue<int> q;
deque<int> dq;
priority_queue<int> pq;
stack<int> st;
vector<char> ch;
 
bool palin()
{
    for (int i = 0; i < ch.size() / 2; i++)
    {
        if (!(ch[i] - ch[ch.size() - 1 - i] == 2 || -2 == ch[i] - ch[ch.size() - 1 - i] || ch[i] == ch[ch.size() - 1 - i]))
        {
            return false;
        }
    }
    return true;
}
 
int main()
{
    int n, k;
    char input;
    cin >> n;
    for (; n--;)
    {
        scanf("%d", &k);
        getchar();
        ch.clear();
        for (int j = 0; j < k; j++)
        {
            scanf("%c", &input);
            ch.push_back(input);
        }
        
        if (!palin())
        {
            printf("NO\n");
        }
        else
        {
            printf("YES\n");
        }
 
    }
    return 0;
}

A번 대회 끝나고 소스를 깔끔하게 정리해봤다.

#include<cstdio>
 
#define abs(x) ((x)<0?-(x):(x))
 
char input[101] = { 0 };
 
int main()
{
    int T, n;
    bool check = false;
    scanf("%d", &T);
    for (; T--;)
    {
        check = false;
        scanf("%d", &n);
        scanf("%s", input);
        for (int i = 0; i < n / 2; i++)
        {
            if (!(input[i] == input[n - i - 1] || abs(input[i] - input[n - i - 1]) == 2)) {
                check = true;
                break;
            }
        }
        if (check)printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}

B번 Numbers on the Chessboard

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
 
using namespace std;
 
typedef long long ll;
typedef unsigned char BYTE;
typedef unsigned int UI;
typedef unsigned short US;
typedef unsigned long long ULL;
 
vector<vector<pair<int, int>>> map;
vector<int> ans;
queue<int> q;
deque<int> dq;
priority_queue<int> pq;
stack<int> st;
vector<char> ch;
 
int main()
{
    ll n, k;
    ll x, y;
    scanf("%lld %lld", &n, &k);
    ll mans;
    for (int i = 0; i < k; i++)
    {
        scanf("%lld %lld", &x, &y);
        if (n == 2)
        {
            if (x == 1 && y == 1)
            {
                printf("1\n");
            }
            else if (x == 1 && y == 2)
            {
                printf("3\n");
            }
            else if (x == 2 && y == 2)
            {
                printf("2\n");
            }
            else
            {
                printf("4\n");
            }
            continue;
        }
        if (x % 2 != 0)
        {
            if (y % 2 != 0)
            {
                mans = (x / 2) * ((n + 1) / 2) + (x / 2) * (n / 2) + (y + 1) / 2;
            }
            else
            {
                mans = (x / 2) * ((n + 1) / 2) + (x / 2) * (n / 2) + (y + 1) / 2 + (n * n + 1) / 2;
            }
        }
        else
        {
            if (y % 2 == 0)
            {
                mans = (x / 2) * ((n + 1) / 2) + ((x - 1) / 2) * (n / 2) + (y + 1) / 2;
            }
            else
            {
                mans = (x / 2) * ((n + 1) / 2) + ((x - 1) / 2) * (n / 2) + (y + 1) / 2 + (n * n) / 2;
            }
        }
        printf("%lld\n", mans);
    }
    return 0;
}

B번 대회 끝나고 소스를 깔끔하게 정리해봤다.

#include<cstdio>
 
typedef long long ll;
 
int main()
{
    ll n, k, x, y;
    ll ans;
    scanf("%lld %lld", &n, &k);
    while (k--)
    {
        scanf("%lld %lld", &x, &y);
        if ((x + y) % 2 == 0)
        {
            ans = (x - 1) * n + y;
            ans = (ans + 1) / 2;
        }
        else
        {
            ans = (x - 1) * n + y;
            ans = (ans + 1) / 2 + (n * n + 1) / 2;
        }
        printf("%lld\n", ans);
    }
}

C번 Minimum Value Rectangle

#include<cstdio>
#include<vector>
#include<deque>
#include<algorithm>
 
using namespace std;
 
vector<int> save;
deque<int> dq;
vector<int> ans;
 
int main()
{
    int T, n, input;
    int max = 0;
    double check = 0;
    scanf("%d", &T);
    for (; T--;)
    {
        save.clear();
        save.resize(10001);
        scanf("%d", &n);
        dq.clear();
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &input);
            save[input]++;
            if (save[input] == 2) {
                dq.push_back(input);
                save[input] = 0;
            }
        }
 
        sort(dq.begin(), dq.end());
 
        if (dq.size() <= 2)
        {
            while (!dq.empty()) {
                for (int i = 0; i < 2; i++)
                {
                    printf("%d ",dq.front());
                }
                dq.pop_front();
            }
            printf("\n");
            continue;
        }
        check = 0;
        double max_d = 0;
        for (int i = 0; i < dq.size() - 1; i++)
        {
            check = 2.0 * (dq[i] + dq[i + 1]) * 2.0 * (dq[i] + dq[i + 1]) / (dq[i] * dq[i + 1]);
            if (max_d == 0 || max_d > check)
            {
                max_d = check;
                ans.clear();
                for (int anan = 0; anan < 2; anan++) {
                    ans.push_back(dq[i]);
                    ans.push_back(dq[i + 1]);
                }
            }
        }
 
        for (int i = 0; i < ans.size(); i++)
        {
            printf("%d ", ans[i]);
        }
        printf("\n");
    }
    return 0;
}

C번 대회 끝나고 소스를 깔끔하게 정리해봤다.

#include<cstdio>
#include<vector>
#include<algorithm>
 
using namespace std;
 
vector<int> cnt;
vector<int> vc;
vector<int> out;
 
int main()
{
    int T, input, n;
    double ans, cal;
    scanf("%d", &T);
    for (; T--;)
    {
        cnt.clear();
        vc.clear();
        scanf("%d", &n);
        cnt.resize(10001);
        for (; n--;)
        {
            scanf("%d", &input);
            cnt[input]++;
            if (cnt[input] == 2)
            {
                cnt[input] = 0;
                vc.push_back(input);
            }
        }
 
        sort(vc.begin(), vc.end());
        ans = 0;
        for (int i = 0; i < vc.size() - 1; i++)
        {
            cal = 4.0 * (vc[i] + vc[i + 1])* (vc[i] + vc[i + 1]) / (vc[i] * vc[i + 1]);
            if (i == 0 || ans > cal)
            {
                ans = cal;
                out.clear();
                out.push_back(vc[i]);
                out.push_back(vc[i + 1]);
            }
        }
        for (int i = 0; i < 4; i++)
        {
            printf("%d ", out[i / 2]);
        }
        printf("\n");
    }
    return 0;
}

A, B, C를 엄청난 실수를 하고 3솔브를 했지만 이번에 의외로 hack 당한 사람이 많아 순위가 많이 오르면서 내 rating도 많이 올라갔다. 이대로 민트까지 가면 좋겠다