카테고리 없음

앳코더 ABC 440 후기

tkd0711 2026. 1. 11. 00:58

AtCoder Beginner Contest 440 회고 (tkd0711)

https://atcoder.jp/contests/abc440

날짜: 2026-01-10 (Sat)
결과 요약:
- A, B: 1트 AC
- C: 대회 중에는 오답, 대회 후 upsolve로 AC
- D: 대회 중에는 구현까지 못 갔고, 이후 아이디어 + 구현 정리
개인 체감:
- A, B까지는 괜찮았지만 C, D에서 막히면서 많이 아쉬웠던 대회.
- 대회 후에 정리하면서 전처리 + 슬라이딩 윈도우, 값 이분탐색 + 금지 카운트라는 중요한 패턴을 확실히 익힌 대회이기도 했다.

1. 전체 총평

이번 ABC 440은 한 줄로 요약하면:

앞부분(A, B)은 무난했지만,
C, D에서 “한 끗 차이”를 잘 못 넘어서 실전 결과는 아쉬웠고,
대신 대회 후 upsolve를 통해 실력적인 성장은 꽤 있었던 대회.

A, B는 큰 어려움 없이 빠르게 해결.
C는 “패턴 자체는 어느 정도 이해했지만,
주기/나머지를 활용한 차원 축소를 못 해서 실전 중에는 해결하지 못함.
D는 “정렬 + 이분탐색 + 카운팅” 느낌까지는 왔지만,
정확한 수식을 세우지 못해서 코드로까지 이어지지 않았다.

대회 직후에는 아쉬움이 컸지만,
C와 D를 다시 풀면서 알고리즘 패턴을 내 것으로 만든 느낌이 있어서,
결국 의미 있는 연습이 된 컨테스트였다.

2. A, B – 워밍업 문제

공통 요약

A, B는 둘 다 구현/간단 수학 수준의 문제였다.
컨테스트 중:
- A: 약 3~4분 사이에 해결
- B: 그보다 더 빠르게 해결
난이도 자체는 높지 않았고,
입력 파싱 + 간단한 수식/조건만 처리하면 되는 문제라 큰 이슈는 없었다.

그래도 A, B를 안정적으로 빠르게 풀었다는 점에서,
초반 속도와 기본기는 나쁘지 않다는 느낌을 받았다.

(코드는 생략)

3. C – Striped Horse: 완탐에서 전처리 + 슬라이딩 윈도우로

문제 요약

길이 N인 칸, 각 칸의 비용 C[1..N].
양의 정수 x를 하나 고른다.
모든 i(1 ≤ i ≤ N)에 대해,
- (i + x) mod 2W < W이면 i번 칸을 칠한다.
이때 칠해지는 칸들의 비용 합의 최솟값을 구하는 문제.
테스트케이스 T개, ΣN ≤ 2e5, ΣW ≤ 2e5.

대회 중 접근

처음 문제를 읽고 떠올린 감각은:

(i + x) mod 2W < W → “길이 2W 주기에서 W개는 칠하고 W개는 쉬는 패턴”이라는 것까지는 이해했다.
그래서 다음과 같이 생각했다:
- “x에 따라 이 패턴이 좌우로 밀리는 거니까,
  처음에 몇 개를 선택할지(i)를 정한 뒤,
  그 이후로 W개 선택 / W개 스킵을 반복해서 시뮬레이션하면 되지 않을까?”

실제로 작성했던 코드는:

i = 0..W까지 “처음에 선택할 칸 수”를 바꾸며 반복.
이후 인덱스를 돌면서 “W개 선택, W개 건너뛰기”를 직접 시뮬레이션하며 비용 합을 계산하는 구조.

문제점:

(i + x) mod 2W < W가 만드는 패턴과
내가 만든 “선택/스킵 로직”이 완전히 일치하지 않아 로직이 꼬이기 쉬웠고,
시간 복잡도도 사실상 O(N × W)에 가까워서,
ΣN, ΣW ≤ 2e5 제약을 고려하면 안전한 풀이가 아니었다.

정리하면,

패턴에 대한 직관은 있었지만,
나머지(mod) 관점에서 차원 축소를 하지 못해 완전탐색에 가까운 코드로 가버렸다.

upsolve 아이디어 – 전처리 + 슬라이딩 윈도우

upsolve에서 중요한 포인트 두 가지를 정리했다.

(i + x) mod 2W만 사용하므로,
사실 i의 절대값이 아니라 i mod 2W만 중요하다.
x를 바꾸면서 (i + x) mod 2W < W 를 만족하는 i들의 집합은,
나머지 축에서 길이 W짜리 연속 구간 하나에 대응한다.

(1) 나머지별 전처리

period = 2 * W

각 나머지별로 비용 합을 모은다:

S[r] = sum of C[i] for all i such that i % period == r
(0 ≤ r < period)

즉:

“나머지가 0인 칸들의 총 비용”
“나머지가 1인 칸들의 총 비용”
…
“나머지가 2W-1인 칸들의 총 비용”

을 S 배열에 저장한다.

이렇게 하면,
원래 N개의 칸을 “같은 나머지끼리는 항상 함께 칠해지므로”
길이 2W짜리 배열 하나로 압축한 셈이 된다.

(2) 선택 구간 = 길이 W짜리 원형 구간

어떤 x에 대해 칠해지는 칸들은,

(i + x) mod 2W < W 를 만족하는 i들이다.
이는 i mod 2W 관점에서 보면,
어떤 시작점에서 길이 W만큼 연속한 나머지 구간에 해당한다.

즉, x를 고르는 것은 곧 S 위에서

“길이 W짜리 원형 연속 구간 하나를 고르는 것”

과 같고,
우리가 구하고 싶은 값은

“S에서 길이 W짜리 원형 구간의 합 중 최솟값”

이다.

(3) 슬라이딩 윈도우

원형 처리를 위해 S를 두 번 이어 붙인 배열 A를 만든다:

A[i] = S[i % period],  i = 0..(2*period-1)

그리고:

초기 윈도우: A[0..W-1]
시작 위치 start = 0..(period-1) 까지 슬라이딩 윈도우로 순회.

슬라이딩 윈도우 템플릿:

long window = 0;
for (int i = 0; i < W; i++) {
    window += A[i];
}
long ans = window;

for (int start = 1; start < period; start++) {
    window -= A[start - 1];
    window += A[start + W - 1];
    ans = Math.min(ans, window);
}

복잡도:

S 만들기: O(N)
슬라이딩 윈도우: O(W)
한 테스트케이스당 O(N + W)
→ ΣN, ΣW ≤ 2e5 내에서 충분히 안전.

C에서 배운 점

예제에서 칠해지는 칸이 (1, 4, 5, 8)처럼 띄엄띄엄 나와서
“슬라이딩 윈도우와는 거리가 있어 보인다”고 느꼈는데,
사실 “i 축”이 아니라 “나머지 축(i mod 2W)”에서 보면
[0, 1] 같은 연속 구간에 해당했다.
앞으로는:
- mod, 주기, 반복 같은 키워드가 보이면
  “원래 인덱스가 아닌 다른 축(나머지, 주기)에서 단순해지지 않는지” 먼저 고민할 것.
- 슬라이딩 윈도우는 항상 원본 배열이 아니라,
  이렇게 전처리로 만든 압축 배열에 적용되는 경우도 많다는 것을 기억할 것.

4. D – Forbidden List 2: “한 끗” 차이의 이분탐색

문제 요약

금지 리스트 A (N개, 모두 서로 다른 정수).
쿼리 (X, Y)에 대해:
- X 이상인 정수들 중,
- 리스트에 없는 수들만 나열했을 때,
- 그 중 Y번째로 작은 값을 구하는 문제.
제약:
- N, Q ≤ 3×10^5
- Ai, Xj ≤ 10^9, Yj ≤ 10^9

대회 중 접근

처음에는:

X부터 시작해서 하나씩 올려가면서,
- 리스트에 없는 수만 세다가 Y번째에서 멈추는 방식을 떠올렸지만,
Y가 최대 1e9라 이 방식은 바로 불가능하다고 판단했다.

그 다음엔:

A를 정렬하고 이분탐색을 활용해야겠다는 감은 있었고,
예를 들어 (X=6, Y=10) 쿼리에서,
- “6 이상에서 Y개를 세려면,
  적어도 15까지는 봐야 하니까
  그 이후를 이분탐색하면 되지 않을까?” 정도까지는 생각이 갔다.
하지만,
- 무엇을 이분탐색할지,
- 어떤 값을 monotone하게 비교할지(허용 수 개수 vs Y)
  이 부분을 깔끔하게 정리하지 못해서,
  결국 코드를 작성하지 못했다.

정리하면,

“정렬 + 이분탐색”이라는 큰 틀은 떠올렸지만,
정작 필요한 수식을 정리하지 못한 채 멈춘 상태였다.

upsolve 아이디어 – missing(X, t)와 t에 대한 이분탐색

핵심은 “t까지 봤을 때 허용 숫자가 몇 개냐”를 세는 것이다.

(1) 어떤 값 t가 답이라고 가정

X 이상 t 이하에서:

전체 정수 개수: total = t - X + 1
그 중 금지 리스트에 있는 수의 개수: forbidden(X, t)
허용된 수(비금지)의 개수:

[
missing(X, t) = total - forbidden(X, t) = (t - X + 1) - forbidden(X, t)
]

우리가 하고 싶은 건:

“missing(X, t) ≥ Y가 되는 가장 작은 t를 찾는 것”

즉, t에 대한 lower_bound 이분탐색 문제로 바뀐다.

(2) forbidden(X, t)는 정렬 + lower/upper_bound로

A를 오름차순으로 정렬하고:

idxX = lower_bound(A, X)
→ 처음으로 A[idxX] ≥ X인 위치
idxR = upper_bound(A, t)
→ 처음으로 A[idxR] > t인 위치

그러면:

forbidden(X, t) = idxR - idxX

이 값이 [X..t] 구간에 있는 금지 수 개수다.

이렇게 하면 missing(X, t)도 바로 계산할 수 있다.

(3) t 이분탐색 범위 설정

금지 수가 전혀 없다고 가정하면:

X 이상에서 Y번째로 작은 수는 당연히 X + Y - 1.

중간에 금지 수가 있으면 그만큼 답이 오른쪽으로 밀린다.
금지 수는 최대 N개이므로,
최대로 밀려봐야 +N 정도라고 볼 수 있다.

따라서 이분탐색 범위를:

left  = X + Y - 1        // 금지 수가 하나도 없으면 이 값이 답
right = X + Y + N        // 최대 금지 수 N개만큼 더 밀린 최악의 경우

로 잡고,
missing(X, t) ≥ Y가 되는 최소 t를 찾으면 된다.

(4) 인덱스 기반 이분탐색으로 구현한 버전

직접 구현할 때는 t값 자체보다,
정렬된 배열의 인덱스를 기준으로 이분탐색하는 형태로 풀었다.

먼저 정렬된 A에 대해:

int left = 0, right = n - 1;
// lower_bound(A, X)
while (left <= right) {
    int mid = (left + right) / 2;
    if (arr[mid] >= X) right = mid - 1;
    else left = mid + 1;
}
int startIdx = left;  // X 이상인 첫 금지 수 인덱스

그 다음, 인덱스 mid ∈ [startIdx..n-1]를 기준으로 이분탐색:

int l = startIdx, r = n - 1;
long nocnt = 0; // 방해(금지) 수 개수

while (l <= r) {
    int mid = (l + r) / 2;
    long t = arr[mid];

    long total   = t - X + 1;           // [X..t] 전체 정수 개수
    long curcnt  = mid - startIdx + 1;  // [X..t] 안에 있는 금지 수 개수
    long truecnt = total - curcnt;      // [X..t] 안의 허용 수 개수

    if (truecnt < Y) {
        // 아직 허용 수를 Y개 못 채웠음 → t까지의 금지 수 curcnt를 기록하고 더 오른쪽으로
        nocnt = curcnt;
        l = mid + 1;
    } else {
        // 이미 충분히 많음 → 왼쪽에서도 될 수 있으니 범위를 줄임
        r = mid - 1;
    }
}

long answer = X + Y - 1 + nocnt;

이 로직에서 answer = X + Y - 1 + nocnt는:

“금지 수가 없으면 X+Y-1이 답인데,
그 사이에 있는 금지 수(nocnt)만큼 오른쪽으로 답이 밀린다”

라는 직관과 정확히 일치한다.

D에서 배운 점

“X 이상에서 Y번째 비금지 수” 문제는
missing(X, t) = (t - X + 1) - forbidden(X, t)
를 기준으로 생각하면 깔끔해진다.
그 다음에는 “답 t에 대한 이분탐색”으로 자연스럽게 이어진다.
이번에는:
- “정렬 + 이분탐색 + 카운트”라는 감각까지만 있고,
- missing = total - forbidden이라는 수식을 끝까지 쓰지 못해서 구현으로 이어지지 못했다.
교훈:
- 합/개수를 세는 문제에서
  “전체 - 방해 요소 = 원하는 값” 구조로 한 번 정리해보고,
  거기에 이분탐색/투 포인터/슬라이딩 윈도우를 얹을 수 있는지 확인하는 습관을 들이자.

5. 멘탈 / 감정 회고

이번 대회는 솔직히 감정적으로 쉽지 않았다.

A, B를 빨리 풀면서 “이번에는 좀 잘 풀릴 수도 있겠다”는 기대가 생겼고,
C에서 계속 애매하게 막히다 보니 답답함과 조급함이 쌓였다.
D는 방향만 잡고 구현을 못 한 채로 끝나서
대회 직후에는 상당한 자존감 하락과 함께 “내가 잘하고 있는 게 맞나” 같은 생각도 들었다.

하지만 대회가 끝난 뒤:

C를 전처리 + 슬라이딩 윈도우로 다시 풀면서,
mod/주기 → 나머지 축에서의 슬라이딩 윈도우라는 새로운 감각을 얻었고,
D를 missing 수식 + 이분탐색 관점에서 다시 보면서,
“답에 대해 이분탐색하고, 내부에서 count를 계산하는 패턴”을 정리할 수 있었다.

그래서 최종적으로는,

결과만 보면 아쉬웠지만,
이 두 패턴을 몸으로 익혔다는 점에서 의미 있었던 대회였다.

6. 앞으로의 계획

패턴 복습
- C 유형:
  - mod / 주기 / 패턴이 섞인 문제를 좀 더 풀어보면서,
    전처리 + 슬라이딩 윈도우 / 투 포인터로 차원을 줄이는 연습을 할 것.
- D 유형:
  - “k번째 허용값 / 비허용값” 류 문제들을 풀어보면서,
    전체 - 금지 = 허용 구조로 수식을 세우고,
    값 이분탐색 + 카운팅 패턴을 익힐 것.
실전에서의 목표
- A, B는 지금처럼 안정적으로 빠르게 해결.
- C에서는:
  - 단순 완전탐색에서 끝나지 않고,
    주기/나머지/전처리 같은 키워드를 한 번 더 떠올려 보기.
- D에서는:
  - “이분탐색 느낌이 난다”에서 멈추지 않고,
    무엇을 기준으로 증가/감소하는지(예: 허용 수 개수)를 수식으로 써 본 뒤,
    그 수식으로 monotone 조건을 잡는 연습을 할 것.
멘탈 관리
- 대회 직후 레이팅/퍼포먼스부터 보지 말고,
  - “오늘 새로 이해한 개념/패턴 1~2개”를 먼저 적어본 뒤,
  - 그 다음에 결과를 확인하는 흐름으로 바꿔 보기.
- 레이팅은 결국 이런 패턴들을 차곡차곡 내 것으로 만든 결과로
  나중에 천천히 따라오는 지표라는 점을 잊지 않기.

이번 ABC 440은
숫자로만 보면 만족스럽지 않았지만,
내용만 놓고 보면 전처리 + 슬라이딩 윈도우,
missing 수식 + 이분탐색이라는 중요한 패턴을
한 번 깊게 연습한 대회였다.

나중에 이 회고를 다시 보면,

“아, 그때 이런 부분에서 막혔었구나.
그래서 지금은 이런 패턴이 익숙해졌지.”

라고 떠올릴 수 있는,
어느 정도 전환점 같은 대회가 될 것 같다.

C:
15961 (회전 초밥) – Gold 4
13422 (도둑) – Gold 4
21921 (블로그) – Silver 3
1522 (문자열 교환) – Silver 1
2531 (회전 초밥) – Silver 1

D:
1300 (K번째 수) – Gold 2
1654 (랜선 자르기) – Silver 2
2805 (나무 자르기) – Silver 2
10816 (숫자 카드 2) – Silver 4

현재글앳코더 ABC 440 후기

tkd0711 님의 블로그

tkd0711 님의 블로그 입니다.

앳코더, AtCoder,

Today :
Yesterday :

tkd0711 님의 블로그

앳코더 ABC 440 후기

AtCoder Beginner Contest 440 회고 (tkd0711)

1. 전체 총평

2. A, B – 워밍업 문제

공통 요약

3. C – Striped Horse: 완탐에서 전처리 + 슬라이딩 윈도우로

문제 요약

대회 중 접근

upsolve 아이디어 – 전처리 + 슬라이딩 윈도우

(1) 나머지별 전처리

(2) 선택 구간 = 길이 W짜리 원형 구간

(3) 슬라이딩 윈도우

C에서 배운 점

4. D – Forbidden List 2: “한 끗” 차이의 이분탐색

문제 요약

대회 중 접근

upsolve 아이디어 – missing(X, t)와 t에 대한 이분탐색

(1) 어떤 값 t가 답이라고 가정

(2) forbidden(X, t)는 정렬 + lower/upper_bound로

(3) t 이분탐색 범위 설정

(4) 인덱스 기반 이분탐색으로 구현한 버전

D에서 배운 점

5. 멘탈 / 감정 회고

6. 앞으로의 계획

'카테고리 없음'의 다른글

티스토리툴바

« 2026/06 »
일	월	화	수	목	금	토
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30