2023 ICPC Seoul Regional 풀어보기

https://www.acmicpc.net/category/detail/4058

 

260310 시작

기한: 2주 (BOJ 연습최대기간)

목표: 등수 기준 아챔진출권인 6문제 이상, 최대한 많이 풀기

좋은 글 - https://sharaelong.com/posts/2023-icpc-seoul-solution 이 있어서 풀이가 보고 싶을 때마다 참고했습니다.

 

최종결산 - 8솔

정신승리버전 - 10솔 (E,L)

 

0310

B - Black Box를 풀었다. 

대회에서 이걸 못 풀고 세 시간 동안 손가락만 빨고 있었다는 게 말이 안 된다. 진짜뭐함??

그때는 멘탈이 흔들려서 코드를 제대로 못 읽었던 것 같다. 지금 다시 보니 코드 읽고 풀이 나오는 데 10분도 안 걸린다.

세그를 잘못 짜서 한참 디버깅했다. 말고도 다른 실수도 두어 개 있었다. 요즘 말도안되는구현실수가 너무 많다. 컴파일에러도 자주 내고 구현할 때 뇌를 빼고 짜나 싶다. 연습의 필요성을 느낀다.

서울 리저널에 이런 문제를 내냐.. 하고 불평을 했었는데, 개쉬운문제라 못 푼 입장에서 불평하면 추한 것 같다.

B 코드

#include <bits/stdc++.h>
using namespace std;
 
int seg[202020 << 2], N, Z[202020], I[202020];
 
void init(int now, int l, int r){
    if (l == r) return seg[now] = 1, void();
    int m = l+r >> 1;
    init(now*2, l, m);
    init(now*2+1, m+1, r);
    seg[now] = seg[now*2] + seg[now*2+1];
}
 
void update(int now, int l, int r, int i) {
    if (l == r) return seg[now] = 0, void();
    int m = l+r >> 1;
    if (i <= m) update(now*2, l, m, i);
    else update(now*2+1, m+1, r, i);
    seg[now] = seg[now*2] + seg[now*2+1];
}
 
int kth(int now, int l, int r, int k) {
    if (l == r) return l;
    int m = l+r >> 1;
    if (seg[now*2] >= k) return kth(now*2, l, m, k);
    else return kth(now*2+1, m+1, r, k-seg[now*2]);
}
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
 
    cin >> N;
    for (int i = 0; i < N; i++) cin >> Z[i];
    init(1,1,N);
 
    swap(Z[0], Z[Z[N-1]%(N-1)]);
    for (int ai = 0, ri = 0, l = N; l >= 2; ri++) {
        int x = Z[ri];
        int tar = kth(1,1,N,ai+1);
        I[tar-1] = x;
        update(1,1,N,tar);
        l--;
        ai = (ai + x - 1) % l;
    }
    I[kth(1,1,N,1)-1] = Z[N-1];
    for (int i = 0; i < N; i++) cout << I[i] << '\n';
}

 

0311
I - Product Delivery를 풀었다. 대회 때는 나 말고 다른 누가 풀었었다. 처음에는 뇌정지가 왔고, 좀 더 생각해 보니 그리디 풀이가 나왔다. 먼가 쉬운 문제였던 것 같은 기억 덕분에 될 것 같긴 했는데, 증명에 좀 시간이 걸렸다. 아직도 엄밀하게 보인 게 맞는지는 모르겠다. 지금 체감상으로는 B보다 더 어렵게 풀었다. 감이많이죽었나 ..

I 코드

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
 
    int l, r, N, now = 0, ans = 1;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> l >> r;
        if (now <= r) 
            now = max(now, l);
        else ans++, now = l;
    }
    cout << ans;
}

H - M.S.I.S가 전혀 감이 안 잡혀서 풀이를 깠다. DP가 어케어케 나온다 ~~ 까지만 보고 점화식은 안 봤다. 좀 더 생각해봐야 할 것 같다. 

 

0312

H 풀이를 이해했고 AC 코드를 작성했다.

열의 두 값 중 큰 값은 무조건 MSIS에 포함되도록 최적해를 만들 수 있다. 큰 값이 포함되지 않는다면 작은 값을 포기하고 큰 값이 포함되도록 잘 옮기는 게 이득이기 때문이다. 즉, 모든 열에서 큰 값을 일단 답에 포함시키고 작은 값을 얼마나 포함시킬지 생각해야 한다. 

작은 값이 MSIS에 포함된다는 것은 열의 두 값이 모두 포함된다는 뜻이다. 두 값이 모두 포함되는 열만 모아서 정렬하면, 위 행과 아래 행이 모두 정렬되어 있을 것이다. 일단 이러한 열을 결정하면, 큰 값만 포함되는 열은 적당히 중간에 끼워넣으면 된다. 따라서 위 행과 아래 행이 모두 증가하도록 열을 고르는 경우 중 답이 최대화되는 것을 찾으면 된다. 

위 행을 정렬시키면, 이 과정을 아래 행에서 lis를 구하는 과정과 비슷하게 생각할 수 있다. 열의 최댓값은 답에 더해져 있으니, 어떤 열의 두 값을 모두 포함시킨다는 것은 해당 열의 작은 값을 답에 더해준다는 뜻이다. 가중치 있는 lis를 푼다는 느낌으로, 제곱 DP 또는 세그 등을 써서 NlogN에 풀 수 있다.

혼자 생각할 때는 max를 무조건 포함시킨다까지 생각했고, min을 어떻게 최대한 포함시킬지 한참 고민했다. 위 아래를 동시에 생각하니 걍 아무 생각이 안 들어서 포기했는데, 한 행을 정렬한다는 사고를 가지고 더 많이 생각했으면 풀 수 있었을 것 같다. 

H 코드

#include <bits/stdc++.h>
using namespace std;
 
int N, seg[50505 << 2];
 
void update(int now, int l, int r, int i, int v) {
    if (i < l or r < i) return;
    if (l == r) {
        seg[now] = max(seg[now],v);
        return;
    }
    int m = l+r >> 1;
    update(now*2, l, m, i, v);
    update(now*2+1, m+1, r, i, v);
    seg[now] = max(seg[now*2], seg[now*2+1]);
}
int query(int now, int l, int r, int s, int e){
    if (r < s or e < l) return 0;
    if (s <= l and r <= e) return seg[now];
    int m = l+r >> 1;
    return max(query(now*2, l, m, s, e), query(now*2+1, m+1, r, s, e));
}
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
 
    cin >> N;
    vector<pair<int,int>> A(N);
    for (int i = 0; i < N; i++) cin >> A[i].first;
    for (int i = 0; i < N; i++) cin >> A[i].second;
    sort(A.begin(), A.end());
    int ans = 0, x = 0;
    for (int i = 0; i < N; i++) ans += max(A[i].first, A[i].second);
    for (int i = 0; i < N; i++){
        int r = query(1,0,50000,0,A[i].second) + min(A[i].first, A[i].second);
        x = max(x, r);
        update(1,0,50000,A[i].second,r);
    }
    cout << ans+x;
}

F를 생각해봤는데 잘 모르겠다. 오늘 갑자기멘탈터져서 집중이 잘 안 된다.

일단 C - Farm와 F - Lucky Draws를 머릿속에 넣어뒀다.

---

잠이 안 와서 연등을 하고 본 대회 때 우리 팀이 풀었던 D - Fraction과 G - Magic Cards를 짰다. 본 대회 때는 D에서 개개개말렸고 G도 풀이 찾는 데 좀 걸렸던 걸로 기억한다. D는 누구나 보자마자 풀이가 나오지만 짜기 싫은 문제고, 재귀든 스택이든 잘 짜고 자잘한 예외 케이스를 잘 처리하면 풀 수 있다. 처음에 틀리길래 추하게 질문게시판을 켰고, 틀리는 케이스를 찾아 풀 수 있었다. 이러면안되는데..

D 코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
struct Frac {
    // a/b
    ll a, b;
    Frac operator+(const Frac& rhs) {
        Frac ret = {a*rhs.b+b*rhs.a, b*rhs.b};
        ll g = gcd(ret.a, ret.b);
        ret.a /= g, ret.b /= g;
        return ret;
    }
    Frac operator/(const Frac& rhs) {
        Frac ret = {a*rhs.b, b*rhs.a};
        ll g = gcd(ret.a, ret.b);
        ret.a /= g, ret.b /= g;
        return ret;
    }
};
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
 
    int N;
    cin >> N;
    auto ASSERT = [](bool cond){ 
        if (cond) return;
        cout << -1; exit(0); 
    };
    char c;
    cin >> c;
    ASSERT(c == '(');
    int cnt = 1;
    function<Frac()> get = [&]() {
        char c;
        Frac a[3];
        for (int i = 0; i < 3; i++) {
            ASSERT(++cnt <= N);
            cin >> c;
            ASSERT(c != ')');
            if (c == '(') a[i] = get();
            else a[i] = Frac(c-'0',1);
        }
        ASSERT(++cnt <= N);
        cin >> c;
        ASSERT(c == ')');
        return a[0]+a[1]/a[2];
    };
    Frac ans = get();
    ASSERT(cnt == N);
    cout << ans.a << ' ' << ans.b;
}

G는 대강 어떤 감성이었는지 기억나서 풀이는 빨리 찾았는데, 문제를 똑바로 안 읽기도 하고 인덱스 범위 체크를 안 해서 한 번 틀렸다. 애매한 제한에 set/map 로그가 좀 신경쓰이긴 했는데, 어케어케 잘 짜니 O(NKlogN) ~ 1억 정도로 만들 수 있었다. 자기 전에 J - Special Numbers를 출력했다.

G 코드

#include <bits/stdc++.h>
using namespace std;
 
map<string,int> ans;
vector<int> chk[505050];
int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
 
    int N, M, K, F;
    cin >> N >> K >> M >> F;
    for (int i = 0; i < K; i++){
        for (int j = 0,x; j < M; j++){
            cin >> x;
            if (chk[x].empty() or chk[x].back() != i) 
                chk[x].push_back(i);
        }
    }
    for (int i = 1; i <= N; i++) {
        string s;
        for (int j = 0, ii = 0; j < K; j++){
            if (ii < chk[i].size() and chk[i][ii] == j) {
                s.push_back('Y');
                ii++;
            }
            else s.push_back('N');
        }
        if (ans.find(s) == ans.end()) ans[s] = i;
        else ans[s] = 0;
    }
    while (F--){
        string t;
        cin >> t;
        cout << ans[t] << '\n';
    }
}

 

0313

개꿀일과덕분에 오전에 고민할 시간이 생겼다.

C, F, J 풀이가 나온 것 같다. 생각보다 빨리 풀려서 기분이 좋아졌다.

J를 먼저 짰다. 각 자릿수를 곱한 수가 가질 수 있는 소인수는 2,3,5,7 뿐이니 k가 2,3,5,7을 몇 개 가지고 있는지 센 뒤 무지성디짓디피를 하면 된다. k가 2,3,5,7 외의 소인수를 가지고 있으면 0이 반드시 포함되어야 한다. 필요한 상태 개수는 필요한 2/3/5/7의 개수의 곱 * 길이 정도인데, 2,3,5,7 개수의 곱은 얼마 안 된다.

L,R 제한이 10^20인 건 무슨 의도일까? 생각하기 싫어서 파이썬으로 짰다. 코드가 길긴 한데 무지성반복이 많아서 구현이 어려운 건지는 잘 모르겠다. 8차원 dp 배열을 선언하는 부분이 제일 복잡했다.

mod 1e9+7을 출력해야 한다는 걸 까먹어서 30분을 버렸다. 

J 코드

k, L, R = map(int,input().split())
 
cnt = [0]*10
while k % 2 == 0:
    cnt[2] += 1
    k //= 2
while k % 3 == 0:
    cnt[3] += 1
    k //= 3
while k % 5 == 0:
    cnt[5] += 1
    k //= 5
while k % 7 == 0:
    cnt[7] += 1
    k //= 7
if k > 1: 
    cnt[0] = 1
 
def f(l, a, b, c, d, e, s, z, X, dp):
    if l == 0:
        return int(a+b+c+d+e == 0)
    if dp[l][a][b][c][d][e][s][z] != -1:
        return dp[l][a][b][c][d][e][s][z]
    ans = 0
    for i in range(10):
        if s == 0 and i > X[l-1]: break
        if z == 0 and i == 0: continue
        ns = int(s or i < X[l-1])
        na, nb, nc, nd, ne = a,b,c,d,e
        if i == 0: 
            na -= 1
            nb = nc = nd = ne = 0
        elif i == 2: nb -= 1
        elif i == 3: nc -= 1
        elif i == 4: nb -= 2
        elif i == 5: nd -= 1
        elif i == 6: 
            nb -= 1
            nc -= 1
        elif i == 7: ne -= 1
        elif i == 8: nb -= 3
        elif i == 9: nc -= 2
        na = max(na, 0)
        nb = max(nb, 0)
        nc = max(nc, 0)
        nd = max(nd, 0)
        ne = max(ne, 0)
        ans += f(l-1, na, nb, nc, nd, ne, ns, 1, X, dp)
    dp[l][a][b][c][d][e][s][z] = ans
    return ans
 
def go(N):
    X = []
    while N:
        X.append(N % 10)
        N //= 10
    dp = [
        [
            [
                [
                    [
                        [
                            [
                                [-1,-1] for s in range(2)
                            ] for e in range(cnt[7]+1)
                        ] for d in range(cnt[5]+1)
                    ] for c in range(cnt[3]+1)
                ] for b in range(cnt[2]+1)
            ] for a in range(cnt[0]+1)
        ] for l in range(len(X)+1)
    ] 
    ret = f(len(X), cnt[0], cnt[2], cnt[3], cnt[5], cnt[7], 0, 0, X, dp)
    for i in range(1, len(X)):
        ret += f(i, cnt[0],cnt[2],cnt[3],cnt[5],cnt[7],1,0,X,dp)
    return ret
 
ans = go(R)
if L > 1: ans -= go(L-1)
print(ans % (10**9+7))

이후 C를 짰다. 농장의 모양에 대한 조건은 히스토그램 모양이라는 뜻이다. 직사각형을 아래로는 원하는 만큼 내릴 수 있으니, 같은 x에 점이 여러 개 있다면 y가 가장 큰 점만 고려해도 된다. 각 x마다 y가 가장 큰 점만 남기면, 직사각형으로 묶을 수 있는 x끼리 최대한 묶는 문제가 된다. 이때 작은 x부터 보며 왼쪽과 최대한 합쳐가는 그리디가 성립한다. 합칠 수 있는 가장 가까운 x와 합치지 않아 얻을 수 있는 이득이 없기 때문이다. 두 x를 합칠 수 있는지는 해당 x의 y좌표와 히스토그램의 높이로 확인할 수 있다. 즉, (높이, y좌표) 쌍을 높이가 단조 증가하도록 스택으로 관리하면 문제를 풀 수 있다. 

 

0314

어제 C AC까진 받았는데, 침대에서 생각해보니 구현 실수를 했었다. 길이가 1인 수평 선분을 더 잘 처리해야 했다. 고쳐서 다시 제출하고 데추주를 올렸다. 기여를 보니 나처럼 푼 사람이 없어 보여서 정당성을 더 생각해 봤는데 맞는 것 같다. y가 높은 점부터 넓게 직사각형을 잡는 그리디 풀이와 동일한 해를 만들 것 같다. 아마?

C 코드

#include <bits/stdc++.h>
using namespace std;
 
int top[1010101], ma[1010101], chk[1010101], N, M;
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
 
    cin >> M >> N;
    int x,y, xma = 0;
    cin >> xma;
 
    for (int i = 2; i < M; i += 2){
        cin >> y >> x;
        if (top[xma] > y) chk[xma] = y;
        top[xma] = max(top[xma], y);
        for (int j = xma+1; j <= x; j++) top[j] = y;
        xma = x;
    }
    cin >> x;
    memset(ma, -1, sizeof ma);
    for (int i = 0; i < N; i++){
        cin >> x >> y;
        ma[x] = max(ma[x], y);
    }
    vector<pair<int,int>> stk;
    int ans = 0;
    for (int i = 0; i <= xma; i++) {
        if (ma[i] == -1) {
            while (stk.size() and stk.back().second > top[i]){
                stk.pop_back();
                ans++;
            }
            if (stk.size()) stk.back().first = min(stk.back().first, top[i]);
            continue;
        }
        while (stk.size() and stk.back().second > top[i]){
            ans++;
            stk.pop_back();
        }
        if (stk.size() and stk.back().first >= ma[i]) 
            stk.back().first = min(stk.back().first, top[i]), stk.back().second = max(stk.back().second, ma[i]);
        else stk.emplace_back(top[i], ma[i]);
        if (chk[i]) {
            while (stk.size() and stk.back().second > chk[i]){
                stk.pop_back();
                ans++;
            }
            if (stk.size()) stk.back().first = min(stk.back().first, chk[i]);
            continue;
        }
    }
    cout << ans+stk.size();
}

F의 풀이라고 생각했던 무지성 그리디의 반례를 찾았다. 짜기 전에 찾아서 다행이다. 그리디는 안 될 것 같고 먼가 O(NK) DP 같은 걸 하고 싶은데 될지 모르겠다. 목표가 6솔+a였는데 생각보다 빨리 달성해서 좀 귀찮아졌다.

 

0316

어제 F 진짜 풀이가 나왔다고 생각했는데, 막상 짜려고 보니 근접했지만 안 되는 풀이였다. 조금 더 생각해서 풀 수 있었다. 

선택하는 점은 반드시 어떤 구간의 끝점 중 하나이다. 고른 점이 끝점이 아니라면 끝점으로 쭉 밀어도 손해를 보지 않기 때문이다. 따라서 각 구간의 끝점만 고려하면 되니 좌표압축을 해 주자. 이제 고려할 점의 수가 O(N)개로 줄었고, f(x, k) 같은 dp를 생각해볼 수 있게 되었다.

점을 고르는 순서는 상관없으니 x가 증가하는 순으로 선택하자. f(x, k) := x 이상인 점만 k개 골랐을 때 최대 구간 개수 같은 식으로 dp 정의를 하면, 이전에 고른 점에 따라 답이 달라지니 안 된다. 방향을 바꿔 f(x, k) := 마지막으로 x를 골랐고 이후 k개를 더 고를 때 최대 구간 개수로 정의하자. x < i인 어떤 i를 x 다음으로 고르면, i를 지나는 구간 중 x를 지나지 않는 구간들을 새로 얻을 수 있다. 이 개수를 C[x][i]로 정의하면, i를 골랐을 때 비용은 f(i, k-1) + C[x][i]가 된다. 따라서 $f(x, k) = \underset{x < i}{\max}(f(i, k-1) + C[x][i])$이고, 이 점화식을 그대로 계산하면 $O(KN^2)$이다.

f(x, k)가 f(*, k-1)만을 참고한다는 점에서 최적화할 수 있어 보이는 점화식이다. 어제는 C[x][i]가 누적합 같은 느낌으로 x에 대한 식과 i에 대한 식으로 분리된다고 생각해서 누적 max같은 개념으로 O(KN)에 될 줄 알았는데, 식이 깔끔하게 안 나온다. 고정된 k에 대해 x가 큰 순으로 f(x,k)를 계산한다고 생각하자. 이때 C[x][i]는 시작점이 x보다 크고 i를 지나는 선분의 개수와 같다. f(x,k)를 계산한 뒤 시작점이 x인 모든 구간을 보며 해당 구간에 포함되는 모든 i에 대해 C[x][i]에 1을 더하면 C[x-1][*]를 얻을 수 있다. f(i, k) + C[*][i]를 세그먼트 트리로 관리하면 구간 추가와 단일 dp값 계산을 O(logN)에 처리할 수 있고, 고정된 K에 대해 N개의 구간이 한 번씩 추가되니 전체 $O(KN \log N)$에 문제를 풀 수 있다.

좀 꼬아서 생각한 탓에 필요없이 복잡하게 짠 부분이 있다. 지금은 메모리도 $O(KN \log N)$만큼 쓰는데, 토글링이 되니 $O(N \log N)$만 써도 된다. -C[x][i] 배열이 monge array를 만족한다나? 해서 어케어케 잘 하면 DnC opt로도 풀 수 있다고 한다.

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
 
vector<vector<int>> seg, lazy;
vector<int> D[20202];
 
void push(int now, int l, int r, int idx) {
    seg[idx][now] += lazy[idx][now];
    if (l != r) {
        lazy[idx][now*2] += lazy[idx][now];
        lazy[idx][now*2+1] += lazy[idx][now];
    }
    lazy[idx][now] = 0;
}
 
void update(int now, int l, int r, int i, int v, int idx) {
    push(now,l,r,idx);
    if (i < l or r < i) return;
    if (l == r){
        seg[idx][now] = v;
        return;
    }
    int m = l+r >> 1;
    update(now*2,l,m,i,v,idx);
    update(now*2+1,m+1,r,i,v,idx);
    seg[idx][now] = max(seg[idx][now*2], seg[idx][now*2+1]);
}
 
void add(int now, int l, int r, int s, int e, int v, int idx) {
    push(now,l,r,idx);
    if (e < l or r < s) return;
    if (s <= l and r <= e) {
        lazy[idx][now] = v;
        push(now,l,r,idx);
        return;
    }
    int m = l+r >> 1;
    add(now*2,l,m,s,e,v,idx);
    add(now*2+1,m+1,r,s,e,v,idx);
    seg[idx][now] = max(seg[idx][now*2], seg[idx][now*2+1]);
}
 
int query(int now, int l, int r, int s, int e, int idx) {
    if (e < l or r < s) return 0;
    if (s <= l and r <= e) return seg[idx][now];
    int m = l+r >> 1;
    return max(query(now*2,l,m,s,e,idx), query(now*2+1,m+1,r,s,e,idx));
}
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
 
    int N, K;
    cin >> N >> K;
    vector<int> comp;
    vector<pair<int,int>> intv(N);
    for (auto&[a,b] : intv) {
        cin >> a >> b;
        comp.push_back(a);
        comp.push_back(b);
    }
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    for (auto&[a,b] : intv) {
        a = lower_bound(comp.begin(), comp.end(), a) - comp.begin() + 1;
        b = lower_bound(comp.begin(), comp.end(), b) - comp.begin() + 1;
        D[a].push_back(b);
    }
    seg = vector<vector<int>>(K+1, vector<int>(comp.size()+5 << 2));
    lazy = vector<vector<int>>(K+1, vector<int>(comp.size()+5 << 2));
    int ans = 0;
    for (int x = comp.size()-1; x >= 0; x--) {
        for (int k = 1; k <= K; k++) {
            int v = query(1,0,comp.size(),x+1,comp.size(),k-1);
            update(1,0,comp.size(),x,v,k);
            ans = v;
        }
        for (int k = 0; k <= K; k++){
            for (auto b : D[x])
                add(1,0,comp.size(),x,b,1,k);
        }
    }
    cout << ans;
}

먼가 K 풀이가 나온 것 같은데.. 난이도에 비해 풀이가 너무 단순한 것 같다. L은 열심히 비비면 될 것 같이 생겨서 더 파 볼지 고민하고 있다.

+ 연등 시간이 남아서 K를 짜 봤다. (당연히) 틀렸다. 왜 틀렸는지는 잘 모르겠는데 안 될 것 같긴 했다.. 내일 풀이까볼것

E를 읽어봤다. 파인애플 피자가 생각난다. 내일 얘도 생각해볼것

 

0317

K 풀이를 읽어봤다. 제곱 디피를 어케 잘 한다는 것 같다. 먼가 잘 안 와닿고 어제 짠 건 왜 안되는지도 모르겠다. 아직 풀 만한 단계가 아닌 듯 하다. E는 해싱 세그 섞어서 어케어케 해 보려고 했는데 잘 안 됐고, 파인애플 피자 풀이에서 KMP를 아호코라식으로 바꾸면 될 것 같다. 일단 아호코라식 설명 글을 몇 개 읽어봤는데, 시간복잡도를 확실히 이해하지 못했다. 

오늘은 이런저런 일에 뜀걸음까지 뛰고 왔더니 시간도 없고 피곤하다.

 

0320

18일에는 코포 버추얼을 돌았다. 어제는 시간도 적고 귀찮았다. 오늘은 아호코라식 연습 문제를 풀었다. 풀고 나서 E를 생각해보니, 트라이 각 노드의 실패 함수 계산을 깊이 낮은 노드부터 해야 해서 그냥 아호코라식만 쓰기는 어렵다. pst를 섞으면 될 것 같다.. 까지 생각하고 너무 풀기 싫어서 풀이를 읽어봤다. 해싱도 잘 하면 되고 아호코라식도 잘 하면 된다고 한다. L이랑 E는 열심히 생각하고 열심히 짜면 풀 수 있을 것 같은데.. 챌린지가 길게 지속될수록 점점 귀찮아진다. 나중에 다이아날먹을 하고 싶어지면 풀어 보려 한다.

 

후기

대회 중에 못 푸는 문제들이 내가 영원히 못 푸는 문제는 아니라는 사실을 알게 됐다. 

내 사전 지식과 사고력으로 풀 수 있는 문제만 다 풀어도 충분하니, 내 능력이 닿는 문제의 풀이에 빠르게 도달할 수 있도록 훈련을 이어가면 충분히 발전 가능성이 있다는 생각이 들었다.

훈련을 어떻게 해야 실력이 늘지는 잘 모르겠다. 그냥 (좋은)문제를 많이 풀고 풀이를 열심히 보고 버추얼을 열심히 돌리고 업솔빙을 열심히 하면 되겠지 정도의 마음가짐만 가지고 있다.

 

공부 방법론이나 마인드셋 등등 조언을 주신다면 감사히 새겨듣겠습니다