뉴비의 2025 ICPC Seoul Regional 예선 후기

서론

처음이자 마지막으로 나가는 ICPC이다. 졸업하기도 하고 나이도 그렇고 올해가 마지막 기회다.

 

PS를 시작한 건 최근은 아니지만 열심히 하기 시작한 게 최근이라서 뉴비라고 적었다. 1년도 안 된 것 같다. 사실 딱히 열심히도 아닌 것 같기도... 하핫

 

1년은 무슨 반년 정도 되는 것 같넹

 

작년에는 ICPC에 관심이 없었던 것 같다. 암튼 열심히 하다 보니 나가고 싶어져서 팀을 만들었다.

팀은 celina324, g_grain, jungh150 이렇게 구성되어 있고, 지지난번 SUAPC에도 이렇게 나갔던 것 같다.

 

워낙 은채랑 지은이 둘 다 학교에서 잘하는 편이기 때문에 1등을 못할 것 같다는 생각은 없었고, 그래서 가장 중요한 건 학교 별 1등 커트라인 넘기기였다. 그래서 골드 다 풀기를 목표로 계속 팀연습을 했었다.

 

---

대회

일단 한국어 문제 먼저 셋이 하나씩 읽어보기로 했다.

그런데 프린트된 문제지가 오는 데 15분은 걸려서 그동안 작은 노트북 화면에서 화면 분할로 옹기종기 모여서 봤다.

A. 최적의 분할 1WA (0:17)

각자 문제를 읽어보다가  celina324가 A가 쉬워 보인다고 하면서 이렇게 풀면 되지 않냐고 물어봤다.

사실 뒤늦게 후기를 적고 있는 상태고 틀렸던 코드는 따로 저장해두지 않아서 잘 기억이 안 나긴 하지만, 대충 앞에서 보면서 최소 인덱스가 달라질 때 자르는 풀이였던 것 같다.

여기서부터 좀 잘못됐는데... 일단 구현에 그나마 자신 있던 jungh150가 코드를 짜기로 해서 짰는데, 사실 난 다른 문제를 보고 있었어서 이 문제를 제대로 이해하지 못한 상태였고 그냥 celina324가 말한 대로 구현을 했다.

그렇게 제출해서 한번 틀린 다음에 문제부터 다시 읽고 풀이를 생각해 보니 반례를 금방 찾을 수 있었다. 내가 코드를 짜기 전에 문제를 읽고 같이 풀이 검증을 좀 하고 짜야 했는데 그러지 못해서 좀 미안했다.

A. 최적의 분할 CORRECT (0:42)

암튼 그래서 jungh150가 A 디버깅을 계속하고, celina324와 g_grain은 같이 F를 보고 있었던 것 같다.

어떻게 풀까 고민을 좀 하다가 다시 보니 n이 3000밖에 안 되길래 n 제곱 dp로 해결하면 되겠다 싶어서 바로 그렇게 구현해서 맞았다.

 

▼코드

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> b(n);
    for (int i = 0; i < n; i++) cin >> b[i];

    vector<vector<int>> adp(n, vector<int>(n));
    vector<vector<int>> bdp(n, vector<int>(n));

    for (int i = 0; i < n; i++) {
        int minidx = i;
        for (int j = i; j < n; j++) {
            adp[i][j] = minidx;
            if (a[j] < a[minidx]) {
                minidx = j;
                adp[i][j] = minidx;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        int minidx = i;
        for (int j = i; j < n; j++) {
            bdp[i][j] = minidx;
            if (b[j] < b[minidx]) {
                minidx = j;
                bdp[i][j] = minidx;
            }
        }
    }

    int ans = 0;
    int s = 0;
    while (s < n) {
        for (int e = n - 1; e >= 0; e--) {
            if (adp[s][e] == bdp[s][e]) {
                s = e + 1;
                ans++;
                break;
            }
        }
    }

    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T = 1;
    for (int i = 0; i < T; i++) {
        solve();
    }
}

F. Inverse Look-and-Say 1WA (0:59)

A를 풀고 나서 F를 보고 있던 celina324와 g_grain 쪽으로 갔더니 간단히 문제 설명을 해줬다. 둘은 그냥 쭉 읽어보면서 풀면 쉬운데 입력 크기가 너무 커서 어떻게 해야 되는지 모르겠다며 규칙을 찾아야 되나 고민하고 있었다.

입력을 봤는데 문자열로 읽는다 쳤을 때 길이가 1000밖에 안되어서 왜 고민 중인 거지? 싶었다. 그래서 그냥 읽으면서 확인하면 되는 거 아니냐고 물어보니 둘이 엥 그러네??? 했다.

그래서 다시 jungh150가 컴퓨터 쪽으로 와서 풀었는데 틀렸다.

F. Inverse Look-and-Say 3WA CORRECT (1:33)

다 같이 디버깅을 하다가 celina324는 I를 보러 가고 jungh150와 g_grain이 F 디버깅을 했다.

위에서 말했듯 좀 시간이 지난 뒤에 후기를 적는 거라 어느 순간에 뭘 고쳐서 제출했는지 정확히는 기억이 안 나지만 대략적인 흐름은 이랬다.

jungh150가 아! 이런 경우도 생각해야 되네 하고 제출하고 틀리고

또 jungh150가 아 이거 때문인가? 하고 제출하고 틀리고

g_grain이 아!! 0이면 어쩌구 저쩌구 해서 jungh150가 아 맞네! 하고 제출하고 틀리고

jungh150가 아 0일 때 이것도 처리해야 되네 하고 제출하고 맞았다.

ㅋㅋㅋ

 

▼코드

#include <bits/stdc++.h>
using namespace std;

void solve() {
    string s;
    cin >> s;

    int n = s.size();

    if (n % 2 == 1) {
        cout << -1 << '\n';
        return;
    }

    string ans = "";
    for (int i = 0; i < n; i += 2) {
        char a = s[i];
        char b = s[i + 1];
        if (a == '0') {
            cout << -1 << '\n';
            return;
        }
        if (b == '0' && i == 0) {
            cout << -1 << '\n';
            return;
        }
        if (i >= 2 && b == s[i - 1]) {
            cout << -1 << '\n';
            return;
        }
        for (int j = 0; j < a - '0'; j++) ans += b;
    }
    
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T = 1;
    for (int i = 0; i < T; i++) {
        solve();
    }
}

I. 이차 방정식 CORRECT (2:47)

풀고 나서 다 같이 I를 봤다. 진짜 어떻게 푸는 건지 감이 안 왔다.

브루트포스가 가능할 것 같기는 한데, 탐색 범위를 구하는 것도 어려웠다.

느낌 상 이것까지 풀어야 본선 진출할 수 있을 것 같은데 감도 안 잡히니까 너무 불안했다.

내 기억이 맞다면 진짜 하나도 모르겠어서 다른 문제도 살짝 들낙해봤던 것 같은데 슼보를 보고 다시 돌아왔던 것 같다.

 

일단 뭐라도 해보자 싶어서 jungh150는 규칙이 보일까 싶어 탐색 범위를 널널하게 잡은 브루트포스 코드를 짜서 돌려보고 있었고, g_grain과 celina324는 옆에서 뭔가 엄청 열심히 적고 있었다.

g_grain이 근의 공식에서 (p^2-4kp) 가 제곱수가 되려면 p에 대한 이차 함수를 그려봤을 때 p=2k 대칭이니까 p의 합은 결국 2k * (p의 개수)라는 엄청난 발견을 해냈다!

그 말을 들은 멍청한 jungh150가 오 대박!! 그러네!! 천재당 그럼 이제 어케 하지?를 시전하고 있을 때, celina324가 자기가 규칙을 찾은 것 같다면서 내 코드를 돌려볼 수 있냐고 물어봤다. 그래서 celina324가 불러주는 예제들을 넣어보니 전부 다 잘 나오는 거다!!

celina324한테 어떻게 한거냐고 물어보니까 뭐라고 설명해줬는데 사실 잘 기억이 안 난다. 너무 흥분한 상태이기도 하고 시간이 많이 남은 상황은 아니었어서 마음이 급해서 이해가 잘 안 됐다.

 

그래서 그냥 답을 어떻게 구하면 되는 건지 물어봐서 jungh150가 그걸 그대로 구현해서 냈고 맞았다.

솔직히 기대 안 하고 냈는데 한 번에 맞아서 깜짝 놀랐고 도파민이 미쳤었고 손이 떨렸었다. 시간도 13분밖에 안 남은 상태로 맞아서 더 그랬다.

다 같이 은채 복복복 삼만번 정도 하고 나서 슼보를 봤더니 우리 학교 중에 3솔 한 팀이 없었기 때문에 본선 진출하겠다고 생각하고 남은 시간을 편하게 보냈던 것 같다.

 

▼코드

#include <bits/stdc++.h>
using namespace std;

void solve() {
    long long k;
    cin >> k;

    long long n = 4 * k * k;
    vector<long long> a;
    for (long long x = 1; x < sqrt(n) + 1; x++) {
        if (n % x == 0) {
            if ((x + n/x) % 2 == 0) {
                a.push_back(x);
                a.push_back(n / x);
            }
        }
    }

    long long sz = a.size();
    cout << sz << ' ' << 2 * k * sz << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T = 1;
    for (int i = 0; i < T; i++) {
        solve();
    }
}

 

그 당시 지은이랑 은채가 한바닥 썼던 증명 ㅜㅜ 은채도 마지막에 손 떨렸대

 

대회 후에 (사실 방금) 다시 증명을 해봤다. 좀 간단히 정리해보겠다.

우선 문제에 나와있는 방정식인 x^2 + px + kp = 0에 근의 공식을 적용한다. 근이 정수여야 하므로 그 식에서 루트 안에 있는 항이 제곱수여야 한다.

참고로,

p가 짝수이면 p^2은 4의 배수고, 루트 안의 항이 4의 배수기 때문에 루트 벗겨도 짝수고, 분자가 전부 짝수여서 전체는 정수

p가 홀수이면 p^2 홀수고 -4kp는 짝수니까 둘을 더한 건 홀수로, 루트 벗겨도 홀수고, 분자가 홀수+홀수여서 짝수니까 전체는 정수

따라서, 루트 안의 항이 제곱수이기만 하면 근은 항상 정수를 만족한다.

(이걸 대회 때는 증명하지 못했는데 자연스럽게 성립하는 거여서 다행이었다.)

루트 안에 있는 항이 제곱수여야 한다는 것을 p^2 - kp = q^2 (q는 정수) 라고 표현한다.

여기서 완전제곱으로 묶기 위해서 4k^2을 더해주고 빼준다. 그러면 (p - 2k)^2 이런 식으로 묶이게 되고, 4k^2은 우항으로 넘긴다.

좌항인 (p - 2k)^2 - q^2에 합차 공식을 적용하면 (p - 2k + q)(p - 2k - q) = 4k^2 이런 식으로 정리할 수 있다.

어느 정도 식 정리는 되었는데, 좀 더 편하게 보기 위해서 p - 2k = p' 라고 치환해보자.

p가 정수니까 p'도 정수여야 하고, q도 정수이다. 두 정수의 곱이 4k^2이라는 것은 둘은 서로 쌍이 되는 4k^2의 약수라는 것이다.

단, 이 두 약수의 차이는 짝수여야 한다. 두 수의 차이가 2q이기 때문이다.

따라서, 4k^2의 약수 쌍(둘 다 4k^2으로 나눠지면서 곱하면 4k^2이 되는 두 수)들을 보면서 차가 짝수인 수들의 개수를 세면 된다.

 

▼대회 이후 수정한 코드

#include <bits/stdc++.h>
using namespace std;

void solve() {
    long long k;
    cin >> k;

    long long n = 4 * k * k;
    long long cnt = 0;
    for (long long x = 1; x < sqrt(n) + 1; x++) {
        if (n % x == 0) {
            if (abs(n/x - x) % 2 == 0) cnt += 2;
        }
    }

    cout << cnt << ' ' << 2 * k * cnt << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T = 1;
    for (int i = 0; i < T; i++) {
        solve();
    }
}

 

대회 종료 12분 전 스코어보드(프리즈 상태)이다. 이때는 106등이었다.

 

---

대회 후

최종 스코어보드이다. 84등으로 마무리했고, 학교 1등으로 본선에 진출하게 되었다.

그리고 학교별 1등 커트라인은 2솔이었다. I를 못 풀어도 갈 수 있었기에 은채는 살짝 아쉬워했지만 나는 그래도 3솔로 당당히? 갈 수 있어서 좋았다!!!

 

제출 기록

 

---

후기

A는 예상보다 티어가 살짝 높았는데 I가 예상보다 좀 낮았다. 나는 수학을 못하는 것 같다.

ICPC 예선을 참여하면서 포기한 것들이 있는데, 그래도 본선에 나갈 수 있어서 후회는 없고 다행인 것 같다.

 

본선 후기로 빨리 써야 하는뎅