AtCoder Beginner Contest 440 후기

2026년 1월 10일에 진행한 AtCoder Beginner Contest 440에 참여했습니다. 4문제를 27분 만에 풀었고, 그 결과 퍼포먼스 1541로 ABC439의 실수를 만회할 수 있었습니다.

A. Octave (+1)

제출: 0:30

$X\times2^Y$를 구하면 됩니다.

B. Trifecta (+1)

제출: 1:38

주어진 배열에서 첫 번째, 두 번째, 세 번째로 작은 값의 인덱스를 각각 구해 주면 됩니다. 이 문제까지 빠르게 풀어내면서, 2분도 지나지 않아 두 문제를 풀게 되었습니다.

C. Striped Horse (+1)

제출: 8:20

먼저 길이 $2W$의 배열 $S$을 만듭니다. $S$의 $k$번째 원소는 입력 배열에서 인덱스를 $2W$로 나눈 나머지가 $k$인 모든 원소의 합입니다. $S$를 구성하고 나면 슬라이딩 윈도우를 이용해 문제의 조건에 부합하는 $x$를 $O(W)$에 구할 수 있습니다.

D. Forbidden List 2 (+1)

제출: 27:10

원래 이분 탐색을 잘 못하는데, 운이 좋게도 풀이가 빠르게 나왔습니다. 배열을 정렬하는 전처리 과정 이후, 쿼리마다 다음 과정을 반복해 줍시다. 먼저 이분 탐색으로 $X$ 이상의 원소 중 가장 앞에 있는 것을 찾습니다. 이러한 원소가 존재하지 않거나, $X+Y$ 이상이라면 $X+Y-1$을 출력합니다. 그렇지 않다면, 그러한 원소의 인덱스를 $T$라 합시다.

이제 이분 탐색을 다시 활용하여 $A_S-X-S+T<Y$를 만족하는 최대의 $S$를 찾습니다. 그러면 정답은 $X+Y+S-T$가 됩니다.

결과

보통 D까지 AC를 받는 데 30분 이상이 걸리는데, 이번에는 20분대에 달성했습니다. 최종 퍼포먼스는 1541이었고, 레이팅은 43점이 올라 1226이 되었습니다. 앞으로 더 노력해서 블루 퍼포도 띄워 보겠습니다.