AtCoder Beginner Contest 421

점수: 300
등수: 7022

 

 

C - Alternated

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        var in = new BufferedReader(new InputStreamReader(System.in));
        var out = new PrintWriter(System.out);

        int N = Integer.parseInt(in.readLine());
        String S = in.readLine();

        // 'A'의 위치를 저장할 리스트
        List<Integer> posA = new ArrayList<>();
        for (int i = 0; i < 2 * N; i++) {
            if (S.charAt(i) == 'A') {
                posA.add(i);
            }
        }

        // A로 시작하는 패턴 (A는 0, 2, 4, ...)에 대한 스왑 횟수 계산
        long sum1 = 0;
        for (int k = 0; k < N; k++) {
            int target = 2 * k; // A는 짝수 인덱스
            sum1 += Math.abs(posA.get(k) - target);
        }

        // B로 시작하는 패턴 (A는 1, 3, 5, ...)에 대한 스왑 횟수 계산
        long sum2 = 0;
        for (int k = 0; k < N; k++) {
            int target = 2 * k + 1; // A는 홀수 인덱스
            sum2 += Math.abs(posA.get(k) - target);
        }

        // 두 경우 중 최소 스왑 횟수 출력
        out.println(Math.min(sum1, sum2));

        out.flush();
        out.close();
    }
}

 

 

• 핵심 아이디어: 인접한 동일 문자가 없는 문자열은 오직 두 가지 형태로만 가능합니다. 하나는 "ABABAB..." (A로 시작), 다른 하나는 "BABABA..." (B로 시작)입니다. 따라서, 주어진 S를 이 두 타겟 문자열 중 하나로 변환하는 최소 스왑 횟수를 계산하고, 그 중 작은 값을 선택합니다.
  • 같은 문자를 스왑하는 것은 무의미하므로, 'A'들의 상대적 순서는 유지됩니다. 즉, S에서 왼쪽부터 k번째 'A'는 타겟에서 왼쪽부터 k번째 'A' 위치로 이동합니다.
  • 각 'A'가 이동하는 거리 |현재 위치 - 타겟 위치|가 해당 'A'를 이동시키기 위한 스왑 횟수입니다. (다른 문자와만 스왑하므로, 거리만큼 스왑 발생)
  • 모든 'A'에 대한 거리 합이 해당 타겟으로 변환하는 총 스왑 횟수입니다.

 

D - RLE Moving

import java.io.*;
import java.util.*;

public class Main {
    // RLE 블록 정보를 저장할 클래스
    static class Move {
        char dir;  // 움직임 방향 (U, D, L, R)
        long count; // 해당 방향으로 움직이는 횟수

        public Move(char dir, long count) {
            this.dir = dir;
            this.count = count;
        }
    }

    public static void main(String[] args) throws IOException {
        var in = new BufferedReader(new InputStreamReader(System.in));
        var out = new PrintWriter(System.out);

        // 1. 입력 받기
        var st = new StringTokenizer(in.readLine());
        long rt = Long.parseLong(st.nextToken()); // 타카하시 초기 행
        long ct = Long.parseLong(st.nextToken()); // 타카하시 초기 열
        long ra = Long.parseLong(st.nextToken()); // 아오키 초기 행
        long ca = Long.parseLong(st.nextToken()); // 아오키 초기 열

        st = new StringTokenizer(in.readLine());
        long n = Long.parseLong(st.nextToken()); // 총 움직임 횟수
        int m = Integer.parseInt(st.nextToken()); // 타카하시 RLE 블록 개수
        int l = Integer.parseInt(st.nextToken()); // 아오키 RLE 블록 개수

        var sMoves = new ArrayList<Move>(); // 타카하시 움직임 리스트
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(in.readLine());
            sMoves.add(new Move(st.nextToken().charAt(0), Long.parseLong(st.nextToken())));
        }

        List<Move> tMoves = new ArrayList<>(); // 아오키 움직임 리스트
        for (int i = 0; i < l; i++) {
            st = new StringTokenizer(in.readLine());
            tMoves.add(new Move(st.nextToken().charAt(0), Long.parseLong(st.nextToken())));
        }

        // 2. 상대적 위치 추적
        long dr = rt - ra; // 행 좌표 차이 (T - A)
        long dc = ct - ca; // 열 좌표 차이 (T - A)

        long totalCount = 0; // 총 만나는 횟수
        int sIdx = 0;        // 타카하시 RLE 블록 인덱스
        int tIdx = 0;        // 아오키 RLE 블록 인덱스

        // 3. RLE 블록을 순회하며 시뮬레이션
        while (sIdx < m && tIdx < l) {
            Move sMove = sMoves.get(sIdx);
            Move tMove = tMoves.get(tIdx);

            // 현재 두 RLE 블록 중 더 짧은 구간의 길이
            long steps = Math.min(sMove.count, tMove.count);

            // 한 스텝당 상대적 위치 변화량 계산
            long drChange = getDrChange(sMove.dir, tMove.dir);
            long dcChange = getDcChange(sMove.dir, tMove.dir);


            // 4. 현재 구간에서 만나는 횟수 계산 (수학적 접근)
            if (drChange == 0 && dcChange == 0) {
                // 변화가 없는 경우:
                // 이미 같은 위치라면, 이 구간 내내 계속 만남
                if (dr == 0 && dc == 0) {
                    totalCount += steps;
                }
            } else if (drChange == 0) {
                // 행 위치 차이는 고정, 열 위치 차이만 변하는 경우:
                // 행 차이가 0이고, 열 차이가 0이 되는 지점 찾기
                if (dr == 0 && dc % dcChange == 0) {
                    long k = -dc / dcChange;
                    if (k >= 1 && k <= steps) {
                        totalCount++;
                    }
                }
            } else if (dcChange == 0) {
                // 열 위치 차이는 고정, 행 위치 차이만 변하는 경우:
                // 열 차이가 0이고, 행 차이가 0이 되는 지점 찾기
                if (dc == 0 && dr % drChange == 0) {
                    long k = -dr / drChange;
                    if (k >= 1 && k <= steps) {
                        totalCount++;
                    }
                }
            } else { // drChange != 0 && dcChange != 0
                // 행, 열 위치 차이 모두 변하는 경우:
                // 두 방정식을 모두 만족하는 k 찾기
                if ((dr % drChange == 0) && (dc % dcChange == 0)) {
                    long k1 = -dr / drChange;
                    long k2 = -dc / dcChange;
                    if (k1 == k2 && k1 >= 1 && k1 <= steps) {
                        totalCount++;
                    }
                }
            }

            // 5. 다음 구간을 위한 위치 업데이트 및 인덱스 이동
            dr += steps * drChange;
            dc += steps * dcChange;

            sMove.count -= steps;
            tMove.count -= steps;

            if (sMove.count == 0)  sIdx++;
            if (tMove.count == 0)  tIdx++;
        }

        out.println(totalCount);
        out.flush();
        out.close();
    }

    // 타카하시와 아오키의 움직임 방향에 따른 dr 변화량 계산
    static long getDrChange(char sDir, char tDir) {
        long drChange = 0;
        if (sDir == 'U') drChange--;
        if (sDir == 'D') drChange++;
        if (tDir == 'U') drChange++;
        if (tDir == 'D') drChange--;
        return drChange;
    }

    // 타카하시와 아오키의 움직임 방향에 따른 dc 변화량 계산
    static long getDcChange(char sDir, char tDir) {
        long dcChange = 0;
        if (sDir == 'L') dcChange--;
        if (sDir == 'R') dcChange++;
        if (tDir == 'L') dcChange++;
        if (tDir == 'R') dcChange--;
        return dcChange;
    }
}

문제 분석

이 문제는 거대한 2차원 그리드 위에서 두 명의 캐릭터, 타카하시와 아오키의 움직임을 추적하는 문제입니다.

• 초기 상태: 타카하시와 아오키는 각각 (Rt, Ct)와 (Ra, Ca)의 초기 위치에 있습니다.
• 움직임: 두 캐릭터는 N번의 이동을 동시에 수행하며, 각 이동은 상하좌우(U, D, L, R) 중 하나입니다.런-렝스 인코딩(RLE) 형태로 압축하여 주어집니다. 예를 들어,
• 'R' 2는 'R' 이동을 2번 반복한다는 의미입니다.
• 핵심: N의 크기가 $10^{14}$로 매우 크기 때문에, 모든 이동을 하나씩 시뮬레이션하는 것은 불가능합니다. 대신, 이동 경로를
• 목표: 총 N번의 이동 중 타카하시와 아오키가 같은 셀에 있는 횟수를 찾아야 합니다.

접근 방법

문제의 핵심은 거대한 N을 효율적으로 처리하는 것입니다. 모든 이동을 시뮬레이션하는 대신, 상대적인 위치 변화를 추적하는 것이 해결의 열쇠입니다.

1. 상대적 좌표 사용: 타카하시와 아오키의 절대 좌표를 각각 추적하는 대신, 두 사람의 위치 차이인 (dr, dc) = (Rt - Ra, Ct - Ca)를 추적합니다. 두 사람이 만나는 지점은 (dr, dc) = (0, 0)인 경우입니다.
2. RLE 압축 해제: N은 크지만, 압축된 이동 문자열의 개수 M과 L은 105로 상대적으로 작습니다. 이 점을 활용하여, 두 개의 RLE 문자열을 동시에 처리하는 투 포인터(Two Pointers) 또는 이터레이터 방식의 접근법을 사용합니다. 각 캐릭터의 이동 경로를 세그먼트별로 순회하며, 두 캐릭터의 위치 차이 변화를 계산합니다.
3. 교점 계산: 각 세그먼트 구간(A_i 또는 B_i번 반복되는 구간)에서 위치 차이 (dr, dc)는 일정한 속도로 이동합니다. 따라서 이 구간 동안 (dr, dc)의 시작점과 끝점을 계산하고, 그 사이에 (0, 0)이 포함되는지 확인하여 교점의 개수를 셉니다. 만약 (dr, dc)가 특정 구간 동안 (0, 0)을 지나는 경우, 그 횟수를 계산하여 정답에 더해줍니다.

시간 복잡도

이 문제의 시간 복잡도는 RLE 문자열의 세그먼트 수에 의해 결정됩니다.

• 우리는 총 M개의 타카하시 세그먼트와 L개의 아오키 세그먼트를 순차적으로 처리합니다.
• 투 포인터 방식으로 이 두 세그먼트를 동시에 순회하기 때문에, 각 세그먼트의 시작과 끝점만 고려하면 됩니다.
• 따라서 전체 시간 복잡도는 **O(M + L)**이며, 이는 주어진 제약 조건(M, L <= 10^5) 내에서 충분히 효율적입니다.

 

복기

• 관찰을 통한 패턴찾기 
• 다양한 문제경험 필요

 

[현재: 그레이,  목표: 브라운]