Notice
Recent Posts
Recent Comments
Link
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |
Tags
- PS
- contest397
- 프로그래머스
- 프로그래밍대회
- atcoder beginner contest
- cp초보
- SQL문제
- 어린 동물 찾기
- PCSQL
- cp
- 집계함수
- ABC
- SQL
- 아픈 동물 찾기
- 파이썬
- contest395
- Python
- MIN
- 코테
- 코딩테스트
- pasql
- 경쟁적프로그래밍
- atcoder
Archives
- Today
- Total
노아
[20250315] Atcoder Beginner Contest 397 본문
점수: 700
등수: 6427
D - Cubes
문제분석
- 문제 개요: 양의 정수 이 주어졌을 때, x^3 - y^3 = N을 만족하는 양의 정수 쌍 (x, y)를 찾아야 함. 쌍이 존재하면 하나를 출력하고, 없으면 -1을 출력.
- 입력:
- N: 양의 정수 (1≤N≤10^18).
- 출력:
- x^3 - y^3 = N을 만족하는 (x, y)가 없으면: -1.
- 존재하면: x와 y를 공백으로 구분해 출력 (하나면 충분).
- 제약:
- 1≤N≤10^18 (64비트 정수 범위 내).
- 시간 제한: 2초 (약 10^8 연산).
- 핵심 관찰:
- x^3 - y^3 = (x - y)(x^2 + xy + y^2) = N.
- x > y, x - y = d라 하면 N = d (x^2 + xy + y^2).
- y = k로 두면 x = k + d, 이를 통해 N = d (3k^2 + 3dk + d^2).
접근방법
- 아이디어: x - y = d 로 두고, 를 1부터 탐색하며 N을 d로 나눈 몫 m = N/d가 3k^2 + 3dk + d^2 형태를 만족하는지 확인.
- N = d (x^2 + xy + y^2).
- x = k + d, y = k 대입: N = d (3k^2 + 3dk + d^2).
- m = N/d = 3k^2 + 3dk + d^2, 이는 k에 대한 이차 방정식:
- 3k^2 + 3dk + (d^2 - m) = 0.
- 최적화:
- d^3 ≤ N 까지만 탐색 (d가 너무 크면 m이 작아져 불가능).
- N이 d로 나누어 떨어지지 않으면 건너뜀.
- 이차 방정식의 양의 정수 해 k를 이진 탐색으로 빠르게 찾음.
- 알고리즘:
- d = 1부터 d3 ≤ N 까지 순회.
- N%d==0이면 m = N/d 계산.
- 이차 방정식 3k^2 + 3dk + (d^2 - m) = 0의 양의 정수 해 k를 이진 탐색으로 찾음.
- k가 존재하면 x = k + d, y = k 출력.
- 없으면 -1 출력.
# 이차 방정식 ax^2 + bx + c = 0의 양의 정수 해를 이진 탐색으로 찾는 함수
def sol(a, b, c):
# 탐색 범위: 0 ~ 6억 (N의 최대값 고려)
l, r = 0, 600000001
while r - l > 1:
mid = (l + r) // 2
# 방정식 값 계산
if a * mid * mid + b * mid + c <= 0:
l = mid # 해가 mid 이상일 가능성
else:
r = mid # 해가 mid 미만일 가능성
# l이 정확한 해인지 확인
if a * l * l + b * l + c == 0:
return l
return -1 # 해가 없으면 -1 반환
# 입력 처리
N = int(input()) # 주어진 N 값
# d = x - y를 1부터 탐색
d = 1
found = False
while d * d * d <= N: # d^3 <= N 조건으로 범위 제한
if N % d != 0: # N이 d로 나누어 떨어지지 않으면 건너뜀
d += 1
continue
m = N // d # m = N/d = 3k^2 + 3dk + d^2
# 이차 방정식: 3k^2 + 3dk + (d^2 - m) = 0
k = sol(3, 3 * d, d * d - m) # a=3, b=3d, c=d^2-m
if k > 0: # 유효한 k를 찾으면 (k는 양의 정수)
x = k + d # x = k + d
y = k # y = k
print(x, y) # (x, y) 쌍 출력
found = True
break
d += 1
# 쌍이 없으면 -1 출력
if not found:
print(-1)코드설명
- sol sol 함수: 이차 방정식 3k^2 + 3dk + (d^2 - m) = 0의 양의 정수 해 k를 이진 탐색으로 찾음.
- l 이 해일 경우 반환, 아니면 -1.
- 메인 로직:
- d를 1부터 증가시키며 d^3 ≤ N 확인.
- N이 d로 나누어 떨어지면 m=N/d 계산.
- k 를 찾아 x=k+d, 로 쌍 구성.
- 쌍 발견 시 출력 후 종료, 없으면 -1 출력
시간복잡도
- d 순회: O(10^6)
- 이진 탐색: O(30)
- 총 시간 복잡도: .
- 성능: 2초 내 (약 108 10^8 연산 가능) 충분히 실행 가능.
E - Path Decomposition of a Tree
문제분석
- 문제 개요: NK개의 정점을 가진 트리가 주어짐. 이 트리를 길이 K인 N개의 경로로 분해할 수 있는지 판단해야 함. 즉, NK개의 정점을 N×K행렬로 표현하여 각 행이 길이 K인 경로가 되고, 모든 정점이 한 번씩 사용되며, 경로 내 인접 정점이 트리의 간선으로 연결되어야 함.
- 입력:
- N : 경로 수 (1 ≤ N).
- K : 각 경로의 길이 (1 ≤ K).
- NK−1 개의 간선: ui, vi(1 ≤ ui < vi ≤ NK).
- 출력:
- 가능하면: Yes.
- 불가능하면: No.
- 제약:
- NK≤2×10^5(정점 수).
- 주어진 그래프는 트리 (연결되고 사이클 없음).
- 핵심 관찰:
- NK개의 정점을 N개의 길이 K 경로로 분해하려면, 각 경로가 트리의 연결된 부분을 따라야 함.
- 트리의 각 정점은 최대 하나의 경로에 속해야 하며, 경로가 끝난 후 남은 정점이 없어야 함.
- 트리의 구조상, 경로 분해는 리프에서 시작해 점진적으로 제거하며 확인 가능.
접근방법
- 아이디어: 트리를 DFS로 탐색하며 서브트리 크기를 계산하고, 길이 K K 경로를 찾아 제거하는 과정을 반복.
- 각 정점의 서브트리 크기(size[v])를 계산.
- size[v] = K이면 경로 하나 완성, 해당 부분을 제거 (size[v] = 0).
- 트리 분해 불가능 조건:
- size[v] > K: 경로 길이 초과.
- cnt ≥ 3: 자식 수가 3 이상 (경로 분기 불가).
- size[v] < K 이고 cnt ≥ 2: 경로 완성 불가.
- 최적화:
- DFS를 스택으로 구현하여 재귀 대신 반복 처리 (스택 오버플로우 방지).
- 트리 특성 활용: 리프에서 루트로 올라가며 경로 분해 확인.
- 알고리즘:
- 트리를 인접 리스트로 구성.
- DFS로 각 정점의 서브트리 크기 계산.
- 조건 위반 시 No, 모두 처리 후 남은 정점 없으면 Yes.
import sys
# 빠른 입력 처리 (큰 입력 대비)
input = sys.stdin.readline
# 입력 처리
N, K = map(int, input().split()) # N: 경로 수, K: 경로 길이
NK = N * K # 총 정점 수
# 인접 리스트로 트리 구성 (0-based 인덱스)
T = [[] for _ in range(NK)] # T[i]: 정점 i의 인접 정점 리스트
for _ in range(NK - 1): # NK-1개의 간선 입력
u, v = map(lambda x: int(x) - 1, input().split()) # 1-based -> 0-based
T[u].append(v) # 양방향 간선 추가
T[v].append(u)
# DFS 스택: (정점, 부모, 상태) - 상태 0: 하강, 1: 상승
st = [(0, -1, 0)] # 초기: 루트 0, 부모 없음(-1), 하강 상태
size = [1] * NK # 각 정점의 서브트리 크기, 초기값 1 (자기 자신)
# DFS를 스택으로 구현
while st:
v, p, t = st.pop() # v: 현재 정점, p: 부모, t: 상태
if t == 0: # 하강 단계: 자식 탐색 준비
st.append((v, p, 1)) # 상승 단계 추가 (나중에 처리)
for u in T[v]:
if u != p: # 부모가 아닌 자식만 탐색
st.append((u, v, 0)) # 자식 노드 하강
else: # 상승 단계: 서브트리 크기 계산 및 조건 확인
cnt = 0 # 유효 자식 수 (size > 0인 자식)
for u in T[v]:
if u != p: # 부모 제외
size[v] += size[u] # 서브트리 크기 갱신
if size[u] > 0:
cnt += 1 # 크기가 0이 아닌 자식 카운트
# 분해 불가능 조건 체크
if size[v] > K or cnt >= 3: # 경로 길이 초과 또는 분기过多
print("No")
exit()
if size[v] < K and cnt >= 2: # 경로 완성 불가 (남은 크기 부족)
print("No")
exit()
if size[v] == K: # 길이 K 경로 완성
size[v] = 0 # 해당 부분 제거 (사용 완료 표시)
# 모든 정점이 경로로 분해되었으면 Yes
print("Yes")
코드설명
- 입력 처리: N, K와 간선을 받아 인접 리스트 T 구성.
- DFS 스택: (v, p, t)로 하강(0)과 상승(1) 단계를 관리.
- 서브트리 크기 계산:
- 하강 시 자식 탐색 준비.
- 상승 시 자식 크기를 합산하고 조건 확인.
- 조건 체크:
- size[v] > K: 경로 길이 초과.
- cnt ≥ 3: 분기점 과다.
- size[v] < K이고 cnt ≥ 2: 경로 부족.
- size[v] = K: 경로 완성, 크기 0으로 리셋.
- 결과: 모든 조건 통과 시 Yes.
시간복잡도
- 트리 구성: O(NK) (간선 수 NK−1 처리).
- DFS:
- 각 정점 방문: O(NK) .
- 각 정점의 인접 정점 확인: 총 간선 수 O(NK−1)=O(NK).
- 총 시간 복잡도: O(NK)(선형 시간).
- 공간 복잡도:
- T: (인접 리스트).
- size, st:.
- 총: .
- 성능: NK≤2×10^5 , 2초 내 충분히 실행 가능.
F - Variety Split Hard
문제분석
- 문제 개요: 길이 N의 정수 수열 A를 두 위치 i와 j(1≤ i < j ≤ N−1)에서 나눠 세 개의 연속 부분 수열 [1,i],[i+1,j],[j+1,N]로 분할. 각 부분의 고유 정수 개수의 합을 최대화해야 함.
- 입력:
- : 수열 길이 (3≤N≤3×10^5).
- A: N개의 정수 (1 ≤ Ai ≤ N).
- 출력: 최대 합 (정수).
- 제약:
- N≤3×10^5 (큰 입력).
- 시간 제한: 2초 (약 10^8 연산).
- 핵심 관찰:
- 각 부분 수열은 비어 있지 않아야 함 (i ≥ 1, j ≤ N − 1, i < j).
- 고유 개수는 중복 제거 후 카운트 (집합 크기).
- i와 j의 선택에 따라 [1,i]와 [i+1,j]의 고유 개수 합을 미리 계산하고, [j+1, N]의 고유 개수를 더하는 방식 가능.
접근방법
- 아이디어: 수열을 세 부분으로 나누는 최대 합을 구하기 위해:
- [1,i]와 [i+1, j]의 고유 개수 합의 최대값을 동적 프로그래밍(DP)과 세그먼트 트리로 계산.
- [j+1, N]의 고유 개수를 뒤에서부터 누적 계산.
- 각 j에 대해 max([1,i]+[i+1,j]) + [j+1,N]를 갱신.
- 핵심:
- prefix[i]: [0, i]의 고유 개수.
- X[i]: 를 두 부분으로 나눈 고유 개수 합의 최대값 (LazySegTree 활용).
- suf: [j + 1, N]의 고유 개수 (집합으로 계산).
- 알고리즘:
- 배열과 초기 LazySegTree 설정.
- 를 세그먼트 트리로 동적 계산.
- 뒤에서부터 를 갱신하며 최대 합 찾기.
- 최적화: LazySegTree로 구간 업데이트와 최대값 쿼리를 효율적으로 처리.
from atcoder.lazysegtree import LazySegTree # AtCoder의 LazySegTree 모듈
inf = 1 << 63 # 큰 값 (최소값으로 사용, 약 9.2e18)
# 입력 처리
n = int(input()) # 수열 길이 N
a = list(map(int, input().split())) # 수열 A
# LazySegTree 연산 정의
def mapping(a, b): return a + b # 지연 값 적용: 덧셈
def comp(a, b): return a + b # 지연 값 합성: 덧셈
# prefix 배열 생성: [0, i]의 고유 개수
prefix = []
pre = set() # 현재까지의 고유 정수 집합
for i in range(n):
pre.add(a[i]) # a[i] 추가
prefix.append(len(pre)) # 고유 개수 저장
# LazySegTree 초기화: 최대값 연산, 초기값 0
dp = LazySegTree(max, -inf, mapping, comp, 0, [0] * n)
idx = [-1] * (n + 1) # 각 정수의 마지막 등장 위치, 초기값 -1
X = [0] * (n + 1) # X[i]: [0, i]를 두 부분으로 나눈 최대 고유 개수 합
# X[i] 계산: 동적 프로그래밍과 세그먼트 트리 활용
for i in range(n):
if idx[a[i]] == -1: # a[i]가 처음 등장
dp.apply(0, i, 1) # [0, i-1] 전체에 +1 (첫 등장으로 고유 개수 증가)
else:
dp.apply(idx[a[i]], i, 1) # [idx[a[i]], i-1]에 +1 (중복 간격 증가)
X[i] = dp.prod(0, i) # [0, i-1]의 최대값을 X[i]로 저장
dp.set(i, prefix[i]) # i 위치에 prefix[i] 설정 (첫 부분 고유 개수)
idx[a[i]] = i # a[i]의 마지막 위치 갱신
# 뒤에서부터 [j+1, N]의 고유 개수 계산 및 최대 합 갱신
suf = set() # [j+1, N]의 고유 정수 집합
ans = 0 # 최대 합
suf.add(a[-1]) # 마지막 원소로 초기화
for i in range(n - 2, 0, -1): # j를 뒤에서부터 탐색 (i는 두 번째 분할점)
ans = max(ans, X[i] + len(suf)) # X[i] + [i+1, N]의 고유 개수
suf.add(a[i]) # suf에 a[i] 추가 (고유 개수 증가)
# 결과 출력
print(ans)
코드설명
- 초기화:
- prefix: [0, i]의 고유 개수 계산.
- dp: LazySegTree로 [0, i]의 두 부분 최대 합 관리.
- X[i] 계산:
- 의 등장 위치에 따라 구간에 1 추가.
- X[i] = max([0, k] + [k+1, i])를 세그먼트 트리로 구함.
- dp.set 으로 설정.
- 최대 합 계산:
- suf로 [j+1,N]의 고유 개수 누적.
- ans=max(X[i]+len(suf)).
시간복잡도
- 총 시간 복잡도: O(nlogn).
- 공간 복잡도: O(n) (세그먼트 트리, 배열 등).
- 성능: , O(3×10^5⋅log3×10^5)≈O(5×10^6), 2초 내 충분.
G - Maximize Distance
문제분석
- 문제 개요: N개의 정점과 M개의 방향 간선을 가진 방향 그래프에서, M개의 간선 중 K개를 선택해 가중치를 1로 설정하고, 나머지는 0으로 유지하여 정점 1에서 정점 N까지의 최단 거리를 최대화해야 함.
- 입력:
- N: 정점 수 (2 ≤ N ≤ 30).
- M: 간선 수 (1 ≤ K ≤ M ≤ 100).
- : 가중치 1로 설정할 간선 수.
- 개의 간선: (uj,vj) (1 ≤ uj,vj ≤ N, uj≠vj).
- 출력: 최대 가능한 최단 거리 (정수).
- 제약:
- N은 작음 (≤30), M도 작음 (≤100).
- 정점 N은 1에서 도달 가능 (트리 아님, 일반 방향 그래프).
- 시간 제한: 2초 (약 10^8 연산).
- 핵심 관찰:
- 최단 거리는 경로 상 가중치 1의 개수로 결정됨 (0 또는 1만 사용).
- 최대 최단 거리 d는 K개의 간선을 적절히 배치해 달성.
- d를 결정 문제로 변환: "최단 거리 d 이상이 되도록 K개 이하의 간선으로 가능?"
보완:
- N과 M의 크기로 완전 탐색 불가능, 효율적 접근 필요.
- 방향 그래프 특성상 경로가 여러 개일 수 있음.
접근방법
- 아이디어: 이진 탐색으로 최대 d d 를 찾고, 각 d d 에 대해 최소 컷을 계산해 K K 이하로 가능한지 확인.
- 결정 문제: "최단 거리 d d 이상이 되려면 최소 몇 개의 간선을 1로 해야 하는가?" → 최소 컷.
- d d 를 이진 탐색으로 조정.
- 그래프 구성:
- 노드: N⋅d개 (i⋅d+j , 는 정점, 는 거리 레벨).
- 간선:
- i⋅d + j → i⋅d + j + 1 (용량 ∞): 거리 단조성.
- u⋅d + j → v⋅d + j (용량 1): 원래 간선 비용.
- u⋅d + j → v⋅d + j + 1(용량 ∞): 거리 증가 제한.
- 소스: 0, 싱크: (N−1)⋅d + d−1.
- 최소 컷: Dinic으로 계산, 컷 크기가 이하이면 가능.
- 알고리즘:
- d를 이진 탐색 (비트 단위).
- 각 에 대해 그래프 구성.
- 최소 컷 계산,와 비교.
- 최대 가능한 출력.
# Dinic 알고리즘 클래스: 최대 유량/최소 컷 계산
class Dinic:
class Edge:
def __init__(self, to, rev, c, oc):
self.to = to # 도착 노드
self.rev = rev # 역방향 간선 인덱스
self.c = c # 잔여 용량
self.oc = oc # 원래 용량
def __init__(self, n):
self.lvl = [0] * n # BFS 레벨
self.ptr = [0] * n # DFS 포인터
self.q = [0] * n # BFS 큐
self.adj = [[] for _ in range(n)] # 인접 리스트
self.inf = 0 # 최대 용량 기준
def addEdge(self, a, b, c, rc=0):
# a -> b에 용량 c, b -> a에 용량 rc 추가
self.adj[a].append(self.Edge(b, len(self.adj[b]), c, c))
self.adj[b].append(self.Edge(a, len(self.adj[a]) - 1, rc, rc))
self.inf = max(self.inf, c, rc) # 최대 용량 갱신
def dfs(self, v, t, f):
if v == t or not f: # 싱크 도달 또는 유량 0
return f
while self.ptr[v] < len(self.adj[v]):
e = self.adj[v][self.ptr[v]]
if self.lvl[e.to] == self.lvl[v] + 1: # 레벨 그래프 따라 이동
p = self.dfs(e.to, t, min(f, e.c))
if p:
self.adj[v][self.ptr[v]].c -= p # 정방향 용량 감소
self.adj[e.to][e.rev].c += p # 역방향 용량 증가
return p
self.ptr[v] += 1
return 0
def calc(self, s, t):
flow = 0 # 총 유량
self.q[0] = s
self.lvl[t] = 1 # 초기 조건
while self.lvl[t]: # 싱크 도달 가능할 때까지
self.lvl = [0] * len(self.q) # 레벨 초기화
self.ptr = [0] * len(self.q) # 포인터 초기화
qi, qe = 0, 1
self.lvl[s] = 1
while qi < qe and not self.lvl[t]: # BFS로 레벨 그래프 생성
v = self.q[qi]
qi += 1
for e in self.adj[v]:
if (not self.lvl[e.to]) and e.c:
self.q[qe] = e.to
self.lvl[e.to] = self.lvl[v] + 1
qe += 1
p = 1
while p: # DFS로 증가 경로 탐색
p = self.dfs(s, t, self.inf)
flow += p
return flow # 최소 컷 크기 반환
# 입력 처리
n, m, k = map(int, input().split()) # N: 정점, M: 간선, K: 가중치 1 개수
u = [0] * m # 간선 시작 정점
v = [0] * m # 간선 끝 정점
for i in range(m):
u[i], v[i] = [int(j) - 1 for j in input().split()] # 0-based 변환
# 이진 탐색으로 최대 d 찾기
ans = 0 # 최대 최단 거리
gap = 16 # 초기 탐색 간격 (N <= 30)
while gap:
mid = ans | gap # 시도할 d 값
flow = Dinic(n * mid) # mid에 대한 그래프 생성
# 거리 단조성 간선 추가
for i in range(n):
for j in range(mid - 1):
flow.addEdge(i * mid + j, i * mid + j + 1, 105) # 용량 105 (무한대 근사)
# 원래 간선에 대한 비용 설정
for i in range(m):
for j in range(mid):
flow.addEdge(u[i] * mid + j, v[i] * mid + j, 1) # 같은 레벨 간선, 비용 1
for j in range(mid - 1):
flow.addEdge(u[i] * mid + j, v[i] * mid + j + 1, 105) # 다음 레벨 제한
# 최소 컷 계산
if flow.calc(0, n * mid - 1) <= k: # 컷 크기가 K 이하이면 가능
ans = mid
gap >>= 1 # 간격 절반으로 줄임
# 결과 출력
print(ans)코드설명
- Dinic: 최대 유량/최소 컷 계산.
- 입력: N,M,K와 간선 리스트.
- 이진 탐색: d를 비트 단위로 탐색.
- 그래프: N⋅d 노드로 구성, 최소 컷 계산.
- 결과: 최대 d 출력.
시간복잡도
- 총 시간 복잡도: O((N^5)MlogN).
- 실제 성능: , O(10^9)내외, 2초 내 실행 가능.
개선점
- D, E, F 난이도 문제에 사용되는 알고리즘 숙지
- A, B, C 난이도의 문제 꼼꼼한 코드 작성
- 시험 10분전 까지 시험 환경 셋팅
[현재: 그레이, 목표: 브라운]
'알고리즘 > CP' 카테고리의 다른 글
| [20250308] Atcoder Beginner Contest 396 (0) | 2025.03.11 |
|---|---|
| [20250301]Atcoder Beginner Contest 395 (0) | 2025.03.10 |
| [20250215]Atcoder Beginner Contest 393 (0) | 2025.02.17 |
'알고리즘/CP' Related Articles
more
