앳코더 ABC 442 후기

JPRS Programming Contest 2026 #1 (ABC 442) 회고 – tkd0711

https://atcoder.jp/contests/abc442

• 날짜: 2026-01-24 (Sat)
• 결과: A ~ D 전부 AC, 총점 1000
  • A: 1트 AC (1:30)
  • B: 1트 AC (3:51)
  • C: 2트 AC (14:08, 자료형 실수 한 번)
  • D: 1트 AC (30:20)
• 전체 느낌:
  • A, B는 안정적으로 풀었고,
  • C에서 조합 계산 + 자료형 체크,
  • D에서 쿼리 구조를 잘 관찰해서 prefix sum 기반으로 정리한 대회였다.

---

1. A, B – 무난한 워밍업

A

• 난이도: 기본 구현/조건 체크 수준.
• 1트 AC, 1분대 해결.
• 입력 읽고 조건 그대로 구현하는 전형적인 A 문제.

B

• 난이도: 간단 구현 + 약간의 사고.
• 1트 AC, 3분대 해결.
• 로직도 단순했고 실수 없이 통과.

---

2. C – Peer Review: 조합 공식 + long 오버플로

문제 요약

• 연구자 1..N, 이해충돌 관계 M개.
• 연구자 i가 단독 저자일 때, 리뷰어 3명은:
  • 저자와 다른 사람.
  • 저자와 이해충돌이 없는 사람.
• 각 i에 대해 “i가 저자일 때 가능한 리뷰어 3인 조합 개수”를 구하는 문제.

아이디어

연구자 i 기준:

• 전체: N
• 저자: 1명
• 저자와 이해충돌 있는 사람 수: deg[i]
• 리뷰어 후보 수:

cand = N - 1 - deg[i]

후보가 cand명 있으면, 가능한 트리플 수는:

candC3 = cand * (cand - 1) * (cand - 2) / 6

구현

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] deg = new int[n + 1];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            deg[a]++;
            deg[b]++;
        }

        for (int i = 1; i <= n; i++) {
            int cand = n - 1 - deg[i];
            if (cand < 3) {
                sb.append(0).append(' ');
                continue;
            }
            long k = (long) cand;
            long comb = k * (k - 1) * (k - 2) / 6;
            sb.append(comb).append(' ');
        }

        System.out.println(sb);
    }
}

실수 포인트

• 처음에는 조합을 int로 계산했다가 오버플로.

• cand 최대가 N-1 ≈ 2×10^5라서
  cand^3가 10^15 수준 → int 범위를 크게 넘는다.

• cand를 long으로 캐스팅해서 계산해야 안전.

---

3. D – Swap and Range Sum: 인접 스왑 + prefix 관찰

문제 요약

• 길이 N 배열 A.

• Q개의 쿼리:

  1. 1 x : A[x]와 A[x+1]를 교환

  2. 2 l r : A[l] + ... + A[r] 계산

• N ≤ 2×10^5, Q ≤ 5×10^5

아이디어

초기 prefix sum:

sum[i] = A[1] + ... + A[i]

을 만들어두고, 1 x 쿼리에서 A[x] = a1, A[x+1] = a2라 하면:

• swap 후:

  • sum[x]만 값이 바뀌고,

  • sum[x+1..N]는 그대로 유지된다.

식으로 보면:

기존: sum[x]   = sum[x-1] + a1
새로운: sum'[x] = sum[x-1] + a2 = sum[x] - (a1 - a2)

따라서:

diff = a1 - a2;
sum[x] = sum[x] - diff;

만 해 주면 된다.

구현

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());

        int[] arr = new int[n + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + arr[i];
        }

        for (int qi = 0; qi < q; qi++) {
            st = new StringTokenizer(br.readLine());
            int type = Integer.parseInt(st.nextToken());

            if (type == 1) {
                int x = Integer.parseInt(st.nextToken());
                int a1 = arr[x];
                int a2 = arr[x + 1];

                int diff = a1 - a2;
                sum[x] = sum[x] - diff;

                arr[x] = a2;
                arr[x + 1] = a1;

            } else {
                int l = Integer.parseInt(st.nextToken());
                int r = Integer.parseInt(st.nextToken());
                int res = sum[r] - sum[l - 1];
                sb.append(res).append('\n');
            }
        }

        System.out.println(sb);
    }
}

D에서 느낀 점

• 인접 swap이라는 조건 덕분에 갱신 위치가 단순해졌다.

• 수식으로 직접 어떻게 변하는지 써 보고,
  그 중 바뀌는 인덱스만 골라서 업데이트한 것이 포인트.

---

4. 이번 대회에서 느낀 점 & 다음 목표

좋았던 점

• A, B를 빠르게 마무리하고 C, D에 집중할 수 있었다.

• C에서는 아이디어는 맞았고, 자료형만 고쳐서 바로 복구.

• D에서는 쿼리 구조를 잘 관찰해서 불필요한 복잡한 자료구조 없이 해결.

다음 목표

• 곱셈이 두 번 이상 등장하면 먼저 long부터 생각하기.

• 쿼리 문제에서:

  • 바로 세그/펜윅으로 가지 않고,

  • 값/합이 어떻게 변하는지 직접 써 보는 습관 유지하기.

• 대회 끝날 때마다 지금처럼 간단 회고를 남기기.

이번 ABC 442는 전체적으로 안정적이었고,
특히 C, D에서 “아이디어는 맞는데 구현 디테일(자료형, 식 관찰)”을 챙기는 연습이 된 대회였다.