[210731] UCPC 2021 예선 후기

 

탈탈 털렸다...

하지만 덕분에 자극이 되기도 한 대회였다.

 

스코어보드는 아래 링크에서 확인가능하다.

https://ucpc.acmicpc.net/contest/scoreboard/668

UCPC 2021 예선

 

밑에 간단하게 그에 대한 후기를 남겨보겠다.

---

나는 D~F를 보고 모두 아이디어가 딱히 떠오르지 않았다. 마침 A~C가 다소 쉬운 듯하다는 소식을 들어 C로 빨리 넘어갔다. C는 간단한 확률/수학 문제였다. 중간에 구현을 조금 잘못하면서 헤매긴 했으나, 빠르게 C번 AC.

 

팀원 한 분께서 B가 BFS문제인데, 이유없이 틀린다는 소식을 들어 B로 넘어갔다.

그런데 아무리 봐도 B가 틀리는 이유를 모르겠어서 열심히 반례를 찾다가 다음 반례를 찾았다.

2 2
1 1
1 2
1 1
2 2
ans: NO
wrong: YES

맨 마지막에 A와 B가 1번 체인지한 이후로 같은지 다른지 추가적으로 확인해주어 B번 AC를 받았다.

 

다음엔 A번과 H번을 살펴봤다.

H번은 다른 팀들이 비교적 많이 AC를 받았길래 그래프쪽에 익숙한 내가 H를, 다른 팀원분이 A를 보러갔다.

H는 최소힙이 아닌 최대힙을 이용한 dijkstra+dp를 이용하여 KCM Travel 문제처럼 접근해보았으나 계속 H번 WA.

나중에 알게 된 사실인데 dijkstra를 이용하지 않고 dp만 이용했어야 됐다.

 

A번은 팀원 한명이 도전했는데, 반례를 아무리 찾아봐도 나오지가 않아 결국 AC를 받지 못했다. A번은 10번 정도 WA를 받은듯 ㅠㅠ

나중에 알고보니 브루트포스로도 충분히 AC가 가능한 진짜 쉬운 문제였다.

너무 어렵게 시도한 듯하다. O(5*5) 정도의 코드인데, 아직도 아래 코드가 왜 틀렸는지 모르겠다.

#include<iostream>
#include<string>
using namespace std;
int main() {
    string s;
    cin >> s;
    int a = -1, b = -1, l = s.length();
    string t1, t2;
    if (l > 1) {
        t1 = s.substr(0, 1);
        t2 = s.substr(1, 1);
        if (stoi(t1) + 1 == stoi(t2))
            a = stoi(t1);
        t1 = s.substr(l - 1, 1);
        t2 = s.substr(l - 2, 1);
        if (stoi(t2) + 1 == stoi(t1))
            b = stoi(t1);
    }
    if (l > 2) {
        t1 = s.substr(0, 1);
        t2 = s.substr(1, 2);
        if (stoi(t1) + 1 == stoi(t2))
            a = stoi(t1);
        t1 = s.substr(l - 2, 2);
        t2 = s.substr(l - 3, 1);
        if (stoi(t2) + 1 == stoi(t1))
            b = stoi(t1);
    }
    if (l > 3) {
        t1 = s.substr(0, 2);
        t2 = s.substr(2, 2);
        if (stoi(t1) + 1 == stoi(t2))
            a = stoi(t1);
        t1 = s.substr(l - 2, 2);
        t2 = s.substr(l - 4, 2);
        if (stoi(t2) + 1 == stoi(t1))
            b = stoi(t1);
    }
    if (l > 4) {
        t1 = s.substr(0, 2);
        t2 = s.substr(2, 3);
        if (stoi(t1) + 1 == stoi(t2))
            a = stoi(t1);
        t1 = s.substr(l - 3, 3);
        t2 = s.substr(l - 5, 2);
        if (stoi(t2) + 1 == stoi(t1))
            b = stoi(t1);
    }
    if (l > 5) {
        t1 = s.substr(0, 3);
        t2 = s.substr(3, 3);
        if (stoi(t1) + 1 == stoi(t2))
            a = stoi(t1);
        t1 = s.substr(l - 3, 3);
        t2 = s.substr(l - 6, 3);
        if (stoi(t2) + 1 == stoi(t1))
            b = stoi(t1);
    }
    if (a == -1 || b == -1) {
        if (l < 4)
            cout << stoi(s) << " " << stoi(s) << "\n";
    }
    else
        cout << a << " " << b << "\n";
}

---

B, C를 해결하여 2솔 뿐인 결과지만, 오히려 공부 자극되고 좋은 경험이었다.

UCPC 2022때는 더 좋은 성적을 거둘 수 있도록 하자. 

UCPC 2022는 100등 이내, UCPC 2023은 본선, UCPC 2024는 본선중에서도 상위권 가보자~