[20250301]Atcoder Beginner Contest 395

점수: 600
등수: 6110

 

 

A - Strictly Increasing?

문제 분석

• 문제: "A - Strictly Increasing?".
• 입력:
  • N: 수열 길이 (2 ≤ N ≤ 100).
  • A: N개의 정수 (1 ≤ A[i] ≤ 1000).
• 조건:
  • 수열 A가 엄격히 증가하는지 확인.
  • 엄격히 증가: 모든 i (1 ≤ i < N)에 대해 A[i] < A[i+1].
• 출력: 엄격히 증가하면 "Yes", 아니면 "No" (대소문자 무관).
• 제약: 시간 2초, 메모리 1024MB.

# 입력 처리
n = int(input())
a = [int(input()) for _ in range(n)]

# 엄격히 증가하는지 확인
is_strictly_increasing = True
for i in range(n-1):
    if a[i] >= a[i+1]:
        is_strictly_increasing = False
        break

# 결과 출력
print("Yes" if is_strictly_increasing else "No")

 

접근 방법

• 아이디어:
  • 수열을 순차적으로 탐색하며, 인접한 두 원소 A[i]와 A[i+1]를 비교.
  • A[i] >= A[i+1]인 경우가 하나라도 있으면 엄격히 증가하지 않음.
• 구현:
  • 리스트로 입력받고, 반복문으로 조건 체크.
  • 플래그 변수로 상태 관리 후 결과 출력.

코드 설명

1. 입력 처리

• 역할: 수열 입력받기.
• 흐름: n 입력 → a 리스트에 N개 정수 저장.

2. 엄격히 증가 확인

• 역할: 수열이 엄격히 증가하는지 검사.
• 흐름: 0부터 n-2까지 a[i]와 a[i+1] 비교 → 조건 위반 시 플래그 변경 후 종료.

3. 결과 출력

• 역할: 결과 출력.
• 흐름: 플래그 기반으로 "Yes" 또는 "No" 출력.

시간 복잡도

• 입력: O(n) (리스트 생성).
• 확인: O(n) (최대 n-1번 비교).
• 총합: O(n) (n ≤ 100 → 약 10^2).
• 결과: 2초 내 충분.

 

B- Make Target

문제분석

• 문제: "B - Make Target".
• 입력:
  • N: 격자 크기 (1 ≤ N ≤ 50).
• 조건:
  • N×N 격자에서, i=1부터 N까지 순서대로:
    • j = N+1-i.
    • i ≤ j일 때, (i,i)부터 (j,j)까지 사각형을 색칠.
    • i가 홀수면 흰색(.), 짝수면 검정(#).
    • 덮어쓰기 가능.
  • 모든 셀이 색칠됨.
• 출력: N줄, 각 줄은 N 길이 문자열 (#: 검정, .: 흰색).
• 제약: 시간 2초, 메모리 1024MB.

# 입력 처리
n = int(input())

# 격자 초기화 (빈 상태: '.')
grid = [['.' for _ in range(n)] for _ in range(n)]

# 색칠 작업
for i in range(n):
    j = n + 1 - i - 1  # j는 0-based 인덱스
    if i <= j:
        color = '#' if i % 2 == 0 else '.'  # 홀수 i는 흰색, 짝수 i는 검정
        for r in range(i, j + 1):
            for c in range(i, j + 1):
                grid[r][c] = color

# 결과 출력
for row in grid:
    print(''.join(row))

 

 

접근방법

• 아이디어:
  • 격자를 초기화 후, 주어진 규칙대로 사각형을 색칠.
  • i가 증가하며 사각형 크기가 줄어들고, 이전 색칠을 덮어씌움.
• 구현:
  • 2D 리스트로 격자 관리.
  • i마다 j 계산 후 조건에 맞게 색칠.
  • 마지막에 격자 출력.

코드설명

1. 입력 처리

• 역할: 격자 크기 입력.
• 흐름: n 입력받음.

2. 격자 초기화

• 역할: N×N 격자 생성.
• 흐름: 모든 셀을 .으로 초기화 (임시 빈 상태).

3. 색칠 작업

• 역할: 규칙대로 격자 색칠.
• 흐름:
  • i를 0부터 n-1까지 순회.
  • j = n-1-i 계산.
  • i ≤ j면, (i,i)부터 (j,j)까지 색칠 (i 짝수: #, 홀수: .).

4. 결과 출력

• 역할: 최종 격자 출력.
• 흐름: 각 행을 문자열로 합쳐 N줄 출력.

시간복잡도

 

• 총합: O(n^3) (n ≤ 50 → 약 1.25×10^5).
• 결과: 2초 내 충분.

 

C - Shortest Duplicate Subarray

문제분석

• 문제: "C - Shortest Duplicate Subarray".
• 입력:
  • N: 수열 길이 (1 ≤ N ≤ 200,000).
  • A: N개의 정수 (1 ≤ A[i] ≤ 1,000,000).
• 조건:
  • 연속된 부분 배열에 같은 값이 2번 이상 등장하는지 확인.
  • 있으면 최단 길이, 없으면 -1.
• 출력: 최단 길이 또는 -1.

# 입력 처리
n = int(input())
a = list(map(int, input().split()))

# 최단 중복 부분 배열 찾기
last_seen = {}  # 각 숫자의 마지막 위치 저장
min_length = float('inf')  # 최소 길이 초기화

for i in range(n):
    if a[i] in last_seen:
        length = i - last_seen[a[i]] + 1  # 현재 위치와 이전 위치 간 길이
        min_length = min(min_length, length)
    last_seen[a[i]] = i  # 현재 위치로 업데이트

# 결과 출력
print(min_length if min_length != float('inf') else -1)

 

접근방법

• 아이디어:
  • 각 숫자의 마지막 위치를 저장.
  • 같은 숫자가 나오면 그 사이 길이를 계산해 최솟값 갱신.
• 구현:
  • 딕셔너리로 위치 추적.
  • 한 번 순회하며 최소 길이 찾기.

코드설명

1. 입력 처리

• 역할: 수열 입력.
• 흐름: n과 a 리스트 입력.

2. 최단 길이 찾기

• 역할: 중복 부분 배열 길이 계산.
• 흐름:
  • last_seen으로 숫자의 마지막 위치 저장.
  • 중복 발견 시 길이 계산, 최소값 갱신.

3. 결과 출력

• 역할: 결과 출력.
• 흐름: 중복 있으면 최소 길이, 없으면 -1.

시간복잡도

• 총합: O(n) (n ≤ 200,000 → 약 2×10^5).
• 결과: 2초 내 충분.

 

D - Pigeon Swap

import sys

input = sys.stdin.readline
print = sys.stdout.write

# 입력: 비둘기/둥지 수 N, 연산 수 Q
N, Q = map(int, input().split())

# 둥지 -> 논리적 라벨 매핑 (초기: 둥지 i -> 라벨 i)
box_to_label = list(range(N))  # 0-based
# 라벨 -> 물리적 둥지 매핑 (초기: 라벨 i -> 둥지 i)
label_to_box = list(range(N))  # 0-based
# 비둘기 -> 물리적 둥지 매핑 (초기: 비둘기 i -> 둥지 i)
pigeon_to_box = list(range(N))  # 0-based

# 연산 처리
for _ in range(Q):
    op = list(map(int, input().split()))
    op_type = op[0]
    
    if op_type == 1:  # Type 1: 비둘기 a를 둥지 b로 이동
        a, b = op[1] - 1, op[2] - 1  # 1-based -> 0-based
        pigeon_to_box[a] = label_to_box[b]  # 비둘기 a를 b의 논리적 둥지로
    
    elif op_type == 2:  # Type 2: 둥지 a와 b 교환
        a, b = op[1] - 1, op[2] - 1  # 1-based -> 0-based
        # 라벨 -> 둥지 매핑 교환
        label_to_box[a], label_to_box[b] = label_to_box[b], label_to_box[a]
        # 둥지 -> 라벨 매핑 갱신
        box_to_label[label_to_box[a]], box_to_label[label_to_box[b]] = a, b
    
    elif op_type == 3:  # Type 3: 비둘기 a의 현재 둥지 출력
        a = op[1] - 1  # 1-based -> 0-based
        current_nest = box_to_label[pigeon_to_box[a]] + 1  # 0-based -> 1-based
        print(f"{current_nest}\n")

 

문제분석

• 문제: "D - Pigeon Swap".
• 입력:
  • N: 비둘기/둥지 수 (1 ≤ N ≤ 10^6).
  • Q: 연산 수 (1 ≤ Q ≤ 3×10^5).
  • Q개의 연산 (타입 1, 2, 3).
• 조건:
  • 초기: 비둘기 i는 둥지 i에.
  • 타입 1: 비둘기 a를 둥지 b로.
  • 타입 2: 둥지 a와 b의 비둘기들 교환.
  • 타입 3: 비둘기 a의 둥지 번호 출력.
• 출력: 타입 3 결과.

접근방법

• 아이디어:
  • 비둘기와 둥지의 관계를 두 배열로 관리.
  • pigeon_to_nest: 비둘기 번호 -> 현재 둥지.
  • nest_to_label: 둥지 번호 -> 라벨 (교환 반영).
  • 타입 2를 단순히 라벨 교환으로 처리해 O(1)로 만듦.
• 구현:
  • 배열 두 개로 상태 추적.
  • 각 연산을 상수 시간에 처리.

코드설명

1. 입력 처리

• 역할: 초기 설정.
• 흐름: pigeon_to_nest와 nest_to_label를 1부터 n까지 초기화.

2. 연산 처리

• 역할: 연산 수행.
• 흐름:
  • 타입 1: pigeon_to_nest[a]를 nest_to_label[b]로 갱신.
  • 타입 2: nest_to_label[a]와 nest_to_label[b] 교환.
  • 타입 3: pigeon_to_nest[a] 출력값 저장.

3. 결과 출력

• 역할: 타입 3 결과 출력.
• 흐름: 저장된 결과 순차 출력.

시간복잡도

• 초기화: O(n).
• 연산:
  • 타입 1: O(1).
  • 타입 2: O(1).
  • 타입 3: O(1).
• 총합: O(n + q) (n ≤ 10^6, q ≤ 3×10^5 → 약 1.3×10^6).
• 결과: 2초 내 충분

 

E - Flip Edge

문제분석

• 문제: "E - Reverse Travel".
• 입력:
  • N: 정점 수 (2 ≤ N ≤ 2×10^5).
  • M: 간선 수 (1 ≤ M ≤ 2×10^5).
  • X: 반전 비용 (1 ≤ X ≤ 10^9).
  • M개의 간선 (u_i, v_i).
• 조건:
  • 1번 정점에서 N번 정점까지 이동.
  • 이동: 간선 따라 1 비용 / 모든 간선 반전 X 비용.
  • N 도달 가능 보장.
• 출력: 최소 비용.

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

# 입력 처리
n, m, x = map(int, input().split())
graph = [[] for _ in range(2 * n)]  # 2N 정점 그래프

# 간선 추가
for i in range(n):
    graph[i].append((i + n, x))      # 원래 -> 반전 (X 비용)
    graph[i + n].append((i, x))      # 반전 -> 원래 (X 비용)

for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append((v, 1))          # 원래 간선 (1 비용)
    graph[v + n].append((u + n, 1))  # 반전 간선 (1 비용)

# 다익스트라
dist = [float('inf')] * (2 * n)
dist[0] = 0
pq = [(0, 0)]  # (비용, 정점)

while pq:
    d, u = heappop(pq)
    if d > dist[u]:
        continue
    for v, cost in graph[u]:
        if dist[v] > d + cost:
            dist[v] = d + cost
            heappush(pq, (dist[v], v))

# 결과 출력
print(min(dist[n-1], dist[2*n-1]))

 

접근방법

• 아이디어:
  • "확장 다익스트라"로 그래프를 2N 정점으로 확장.
  • 간선:
    • 원래 간선 (u -> v, 비용 1).
    • 반전 간선 (v+N -> u+N, 비용 1).
    • 반전 전환 (u -> u+N, 비용 X) 및 (u+N -> u, 비용 X).
  • 1에서 N 또는 2N까지의 최단 거리 중 최소값 계산.
• 구현:
  • 인접 리스트로 그래프 구성.
  • 다익스트라로 최단 경로 탐색.

코드설명

1. 입력 처리

• 역할: 그래프 준비.
• 흐름: n, m, x 입력, 2N 크기 인접 리스트 초기화.

2. 간선 추가

• 역할: 그래프 구축.
• 흐름:
  • 반전 간선: i -> i+n (X 비용), i+n -> i (X 비용).
  • 원래 간선: u -> v (1 비용).
  • 반전 간선: v+n -> u+n (1 비용).

3. 다익스트라

• 역할: 최단 경로 계산.
• 흐름:
  • 우선순위 큐로 최소 비용 정점 탐색.
  • 각 정점까지 거리 갱신.

4. 결과 출력

• 역할: 최소 비용 출력.
• 흐름: dist[n-1] (원래 N)와 dist[2*n-1] (반전 N) 중 작은 값 출력.

시간복잡도

• 그래프 구축: O(n + m) (정점 N + 간선 M).
• 다익스트라: O((n + m) log n) (정점 2N, 간선 N+2M).
• 총합: O((n + m) log n) (n, m ≤ 2×10^5 → 약 10^6).
• 결과: 2초 내 충분 (10^8 연산 대비 여유).

 

F - Smooth Occlusion

문제분석

• 문제: "F - Smooth Occlusion".
• 입력:
  • N: 치아 수 (2 ≤ N ≤ 2×10^5).
  • X: 인접 치아 차이 제한 (1 ≤ X ≤ 10^9).
  • N개의 (U_i, D_i): 상단/하단 치아 길이 (1 ≤ U_i, D_i ≤ 10^9).
• 조건:
  • 모든 i에 대해 U_i + D_i = H (일정).
  • 인접 상단 치아 차이 |U_i - U_i+1| ≤ X.
  • 치아 길이 줄이기: 1 비용으로 1 감소.
• 출력: 최소 비용.

# 입력 처리
n, x = map(int, input().split())
teeth = []
for _ in range(n):
    u, d = map(int, input().split())
    teeth.append((u, d))

# H가 가능한지 체크하는 함수
def check(h):
    # 상단 치아 구간이 비지 않는지 확인
    interval_l = 0
    interval_r = h
    for u, d in teeth:
        # 이전 구간 [l, r]에서 다음 구간 계산
        # - 거리 X 이하: [l - x, r + x]
        # - 줄여서 가능한: [h - d, u]
        # 두 구간의 교집합
        interval_l = max(interval_l + d, h + x, x + d) - x - d
        interval_r = min(interval_r + x, u)
        
        # 구간이 비면 False
        if interval_l > interval_r:
            return False
    return True

# H의 상한: min(U[i] + D[i]) + 1
r = min(u + d for u, d in teeth) + 1
# H의 하한: min(X, R-1)
l = min(x, r - 1)

# 이진 탐색
while l + 1 < r:
    m = (l + r) // 2
    if check(m):
        l = m
    else:
        r = m

# 결과 계산: Σ(U[i] + D[i]) - L * N
total = sum(u + d for u, d in teeth) - l * n
print(total)

 

접근방법

• 아이디어:
  • 최종 치아 높이 합 H를 고정하면 비용 = Σ(U_i + D_i) - N * H.
  • 가능한 최대 H를 찾아 비용 최소화.
  • H가 조건을 만족하는지 체크 후 이진 탐색으로 최대 H 탐색.
• 구현:
  • H 고정 시, U_i 구간 계산: H - D_i ≤ U_i ≤ U_i, |U_i - U_i+1| ≤ X.
  • 구간이 유효한지 O(N)으로 확인.
  • 이진 탐색으로 O(N log H) 해결.

코드설명

1. 입력 처리

• 역할: 치아 정보 입력.
• 흐름: n, x와 teeth 리스트 입력 (U_i, D_i 쌍).

2. H 체크 함수

• 역할: H가 가능한지 확인.
• 흐름:
  • 초기 U_1 구간: [0, H].
  • 각 i마다 U_i 구간 갱신: max(L - X, H - D_i) ≤ U_i ≤ min(R + X, U_i).
  • 구간이 비면 False.

3. 이진 탐색

• 역할: 최대 H 찾기.
• 흐름:
  • H 범위: 0 ~ min(Σ(U_i + D_i), X).
  • 중간값 체크하며 left 갱신.

4. 결과 출력

• 역할: 최소 비용 계산.
• 흐름: Σ(U_i + D_i) - N * H 출력.

시간복잡도

• 체크 함수: O(n) (각 치아 1번 확인).
• 이진 탐색: O(log H) (H ≤ 10^9).
• 총합: O(n * log H) (n ≤ 2×10^5 → 약 6×10^6).
• 결과: 2초 내 충분.

 

잘한점

• 6900-> 6100으로 등수가 상승했다.
• 이전 시험에서 미숙했던 시험 사전 준비가 능숙해졌다.

아쉬운점

• D~F문제에 대한 문제풀이시간 확보가 어려웠다.
• D문제부터 문제에 대한 접근방법이 전혀 떠오르지 않았다.

 

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