[20250308] Atcoder Beginner Contest 396

점수:  1000(4/7)
등수:  3879

 

 

 

C - Buy Balls

문제분석

• 문제: "C - Buy Balls".
• 입력:
  • N: 검은 공 개수 (1 ≤ N ≤ 2×10^5).
  • M: 흰 공 개수 (1 ≤ M ≤ 2×10^5).
  • B_i: 검은 공 값 (-10^9 ≤ B_i ≤ 10^9).
  • W_j: 흰 공 값 (-10^9 ≤ W_j ≤ 10^9).
• 조건:
  • 검은 공 개수 ≥ 흰 공 개수.
  • 선택한 공의 값 합 최대화.
• 출력: 최대 합.

# 입력 처리
n, m = map(int, input().split())
b = list(map(int, input().split()))  # 검은 공 값
w = list(map(int, input().split()))  # 흰 공 값

# 내림차순 정렬
b.sort(reverse=True)
w.sort(reverse=True)

# 누적 합 및 최대값 계산
b_sum = [0] * (n + 1)
w_sum = [0] * (m + 1)
w_max = [0] * (m + 1)
for i in range(n):
    b_sum[i + 1] = b_sum[i] + b[i]
for i in range(m):
    w_sum[i + 1] = w_sum[i] + w[i]
    w_max[i + 1] = max(w_max[i], w_sum[i + 1])

# 최대 합 찾기
ans = 0
for i in range(n + 1):  # 검은 공 i개 선택
    max_white = min(i, m)  # 흰 공 최대 개수
    total = b_sum[i] + w_max[max_white]
    ans = max(ans, total)

print(ans)

 

접근방법

• 아이디어:
  • 검은 공과 흰 공을 값 기준 내림차순 정렬.
  • 검은 공 개수(i)를 고정하고, 가능한 흰 공 개수(0~min(i, m)) 중 최대 합을 빠르게 계산.
  • 흰 공 누적 합의 최대값을 미리 구해 O(1)로 처리.
• 구현:
  • 누적 합과 최대값 배열 생성.
  • 검은 공 개수별로 최대 합 갱신.

코드설명

1. 입력 처리

• 역할: 공의 값 입력.
• 흐름: n, m, b, w 입력.

2. 정렬 및 누적 합

• 역할: 값 정렬과 합 계산 준비.
• 흐름:
  • b, w 내림차순 정렬.
  • b_sum: 검은 공 누적 합.
  • w_sum: 흰 공 누적 합.
  • w_max: 흰 공 누적 합의 최대값.

3. 최대 합 찾기

• 역할: 조건 만족 최대 합 계산.
• 흐름:
  • i: 검은 공 개수 (0~N).
  • max_white: 흰 공 최대 개수 (min(i, m)).
  • total: b_sum[i] + w_max[max_white].
  • ans 갱신.

4. 결과 출력

• 역할: 최대 합 출력.
• 흐름: ans 출력.

시간복잡도

• 정렬: O(n log n + m log m) (≈ 10^6).
• 누적 합: O(n + m) (≈ 4×10^5).
• 탐색: O(n) (≈ 2×10^5).
• 총합: O(n log n + m log m) (≈ 10^6).
• 결과: 2초 내 충분 (10^8 대비 여유).

 

D - Minimum XOR Path

문제분석

• 문제: "D - Minimum XOR Path".
• 입력:
  • N: 정점 수 (2 ≤ N ≤ 10).
  • M: 간선 수 (N-1 ≤ M ≤ N*(N-1)/2).
  • M개의 (u_i, v_i, w_i): 간선 정보 (w_i < 2^60).
• 조건:
  • 단순 연결 무방향 그래프.
  • 1에서 N까지 단순 경로의 간선 XOR 최소값.
• 출력: 최소 XOR 값.

# 입력 처리
n, m = map(int, input().split())
graph = [[] for _ in range(n)]  # 인접 리스트
for _ in range(m):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append((v, w))
    graph[v].append((u, w))  # 무방향 그래프

# DFS로 최소 XOR 찾기
def dfs(vertex, xor_val, visited):
    global ans
    if vertex == n - 1:  # 목표 정점 N에 도달
        ans = min(ans, xor_val)
        return
    
    for next_vertex, weight in graph[vertex]:
        if not visited[next_vertex]:
            visited[next_vertex] = True
            dfs(next_vertex, xor_val ^ weight, visited)
            visited[next_vertex] = False  # 백트래킹

# 초기 설정 및 실행
ans = 1 << 60  # 2^60으로 초기화
visited = [False] * n
visited[0] = True  # 시작 정점 방문 표시
dfs(0, 0, visited)
print(ans)

 

접근방법

• 아이디어:
  • DFS로 1에서 N까지 모든 단순 경로 탐색.
  • 경로별 XOR 값을 계산하며 최소값 갱신.
  • 방문 배열로 중복 정점 방지, 백트래킹 사용.
• 구현:
  • 인접 리스트로 그래프 표현.
  • 재귀 DFS로 경로 탐색.

코드설명

1. 입력 처리

• 역할: 그래프 구축.
• 흐름:
  • n, m 입력.
  • graph에 (정점, 가중치) 쌍 추가, 무방향 처리.

2. DFS 함수

• 역할: 경로 탐색 및 XOR 계산.
• 흐름:
  • vertex가 N-1이면 XOR 값으로 ans 갱신.
  • 미방문 이웃 정점으로 재귀 호출, 방문 해제하며 백트래킹.

3. 초기 설정 및 실행

• 역할: DFS 시작.
• 흐름:
  • ans를 2^60으로 초기화.
  • visited로 방문 관리, 0번 정점에서 시작.

4. 결과 출력

• 역할: 최소 XOR 출력.
• 흐름: ans 출력.

시간복잡도

• 그래프 구축: O(m) (m ≤ 45).
• DFS:
  • 단순 경로 수: 최악 O(2^N) (N ≤ 10).
  • 각 정점당 이웃 확인: O(N).
  • 총합: O(2^N * N) (≈ 10^4).
• 총합: O(m + 2^N * N) (≈ 10^4).
• 결과: 2초 내 충분 (10^8 대비 여유).

 

E - Min of Restricted Sum

문제분석

• 문제: "E - Min of Restricted Sum".
• 입력:
  • N: 수열 길이 (1 ≤ N ≤ 2×10^5).
  • M: 조건 수 (0 ≤ M ≤ 10^5).
  • M개의 (X_i, Y_i, Z_i): XOR 조건.
• 조건:
  • A[X_i] ^ A[Y_i] = Z_i.
  • A의 합 최소화.
• 출력:
  • 불가능: -1.
  • 가능: 최소 합 수열.

from collections import deque

# 입력 처리
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    graph[x].append((y, z))
    graph[y].append((x, z))

# BFS로 연결 요소 탐색 및 값 할당
def bfs(start, visited, val):
    queue = deque([start])
    visited[start] = True
    val[start] = 0
    component = [start]
    
    while queue:
        v = queue.popleft()
        for u, w in graph[v]:
            if not visited[u]:
                visited[u] = True
                val[u] = val[v] ^ w
                component.append(u)
                queue.append(u)
            elif val[u] != (val[v] ^ w):  # 조건 불일치
                return None
    return component

# 연결 요소별 최소화
visited = [False] * n
val = [0] * n  # 초기값 0으로 설정
ans = [0] * n

for start in range(n):
    if not visited[start]:
        component = bfs(start, visited, val)
        if component is None:
            print(-1)
            exit()
        
        # 비트별로 합 최소화
        for bit in range(30):  # Z_i ≤ 10^9 < 2^30
            ones = sum(1 for v in component if val[v] & (1 << bit))
            zeros = len(component) - ones
            if ones > zeros:  # 0이 더 적으면 1로 뒤집기
                for v in component:
                    ans[v] |= (1 << bit) if not (val[v] & (1 << bit)) else 0
            else:  # 1이 더 적으면 그대로
                for v in component:
                    ans[v] |= (1 << bit) if val[v] & (1 << bit) else 0

# 결과 출력
print(*ans)

 

접근방법

• 아이디어:
  • 그래프의 연결 요소별로 BFS로 값을 할당.
  • 조건 충돌 시 -1.
  • 비트별로 0과 1의 개수 비교 후 합 최소화.
• 구현:
  • 무방향 그래프 구축.
  • BFS로 값 채우기.
  • 비트 단위 최적화.

코드설명

1. 입력 처리

• 역할: 그래프 생성.
• 흐름: n, m 입력, graph에 (정점, XOR 값) 추가.

2. BFS 함수

• 역할: 연결 요소 탐색 및 값 설정.
• 흐름:
  • 시작 정점에서 val=0 설정.
  • 이웃에 대해 val[u] = val[v] ^ w 계산.
  • 조건 불일치 시 None 반환.

3. 연결 요소 처리

• 역할: 전체 탐색 및 최소화.
• 흐름:
  • 미방문 정점에서 BFS 호출.
  • 연결 요소별로 비트 단위 분석:
    • 1의 개수 > 0의 개수: 0을 1로 뒤집기.
    • 그렇지 않으면: 기존 값 유지.
  • ans에 최적화된 값 저장.

4. 결과 출력

• 역할: 수열 출력.
• 흐름: ans 출력.

시간복잡도

• 그래프 구축: O(m).
• BFS: O(n + m) (모든 정점/간선 1번).
• 비트 처리: O(n * 30) (30비트).
• 총합: O(n + m) (≈ 3×10^5).
• 결과: 3초 내 충분.

 

F - Rotated Inversions

문제분석

• 문제: "F - Rotated Inversions".
• 입력:
  • N: 수열 길이 (1 ≤ N ≤ 2×10^5).
  • M: 모듈러 값 (1 ≤ M ≤ 2×10^5).
  • A_i: 수열 값 (0 ≤ A_i < M).
• 조건:
  • k = 0 ~ M-1에 대해 B_i = (A_i + k) % M.
  • 각 B의 inversion 수 계산 (i < j이면서 B_i > B_j인 쌍 수).
• 출력: M줄, 각 k에 대한 inversion 수.

from atcoder.fenwicktree import FenwickTree

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

# 값별 인덱스 저장
g = [[] for _ in range(m)]
for i in range(n):
    g[a[i]].append(i)

# 초기 inversion 수 계산
ft = FenwickTree(m)
ans = 0
for i in a:
    ans += ft.sum(i + 1, m)  # i보다 큰 값들의 개수
    ft.add(i, 1)            # i 추가

print(ans)

# k = 1 ~ M-1에 대해 변화 계산
for c in range(1, m):
    c1, c2 = 0, 0
    # m-c 값이 0으로 넘어갈 때 inversion 변화
    for idx, val in enumerate(g[m - c]):
        c1 += val - idx                # 왼쪽으로 이동하며 감소
        c2 += n - 1 - val - (len(g[m - c]) - 1 - idx)  # 오른쪽으로 이동하며 증가
    ans += c1 - c2
    print(ans)

 

접근방법

• 아이디어:
  • 초기 B (k=0)의 inversion 수를 펜윅 트리로 계산.
  • k가 증가할 때마다 값이 1씩 증가하며 M-1에서 0으로 넘어가는 변화만 추적.
  • 각 값의 위치를 저장해 inversion 변화량 계산.
• 구현:
  • g: 각 값의 인덱스 리스트.
  • 초기 inversion 계산 후 k별 변화량 추가.

코드설명

1. 입력 처리

• 역할: 수열과 인덱스 저장.
• 흐름:
  • n, m, a 입력.
  • g[i]: 값 i가 나타나는 인덱스 리스트.

2. 초기 inversion 수 계산

• 역할: k=0일 때 inversion 수 구하기.
• 흐름:
  • 펜윅 트리로 i보다 큰 값 개수 합산.
  • 각 i를 트리에 추가하며 ans 갱신.

3. k별 변화 계산

• 역할: k 증가 시 inversion 변화.
• 흐름:
  • m-c: k 증가로 0이 되는 값.
  • c1: 왼쪽으로 이동하며 감소하는 inversion.
  • c2: 오른쪽으로 이동하며 증가하는 inversion.
  • ans += c1 - c2로 갱신.

4. 결과 출력

• 역할: 각 k에 대한 결과 출력.
• 흐름: 초기 ans 출력 후 변화 적용하며 출력.

시간복잡도

• 초기화: O(n) (g 구축).
• 초기 inversion: O(n log m) (펜윅 트리).
• k별 변화:
  • 각 c마다 g[m-c] 순회: O(n) 총합.
  • 총합: O(m * n) (최악 4×10^10, 초과 위험).

 

G - Flip Row or Col

문제분석

• 문제: "G - Flip Row or Col".
• 입력:
  • H: 행 수 (1 ≤ H ≤ 2×10^5).
  • W: 열 수 (1 ≤ W ≤ 18).
  • A_i,j: H×W 격자 (0 또는 1).
• 조건:
  • 연산 X: 행 뒤집기.
  • 연산 Y: 열 뒤집기.
  • 최종 1의 개수 최소화.
• 출력: 최소 1 개수.

# 입력 처리
h, w = map(int, input().split())
row_bits = [int(input(), 2) for _ in range(h)]  # 각 행을 비트로 변환

# DP 테이블 초기화: dp[j][bit] = 열 상태가 bit일 때 j번 뒤집은 행의 개수
dp = [[0] * (1 << w) for _ in range(w + 1)]
for bit in row_bits:
    dp[0][bit] += 1

# 열 뒤집기 반영
for i in range(w):
    for j in range(i, -1, -1):
        for bit in range(1 << w):
            if dp[j][bit]:
                dp[j + 1][bit ^ (1 << i)] += dp[j][bit]

# 최소 1의 개수 계산
ans = float('inf')
for bit in range(1 << w):
    total = 0
    for i in range(w + 1):
        ones = i  # 열 상태 bit에서 뒤집기 i번 했을 때 1의 개수
        total += min(ones, w - ones) * dp[i][bit]  # 행별 최소값
    ans = min(ans, total)

print(ans)

 

접근방법

• 아이디어:
  • 열 뒤집기를 비트마스크(0~2^W-1)로 완전 탐색.
  • 각 열 상태에서 행의 초기 비트 패턴을 DP로 계산.
  • 행 뒤집기 횟수별 최소 1 개수를 구해 총합 최소화.
• 구현:
  • 행을 비트로 변환.
  • DP로 열 뒤집기 상태 전이.
  • 각 상태에서 최적 행 뒤집기 계산.

코드설명

1. 입력 처리

• 역할: 격자 입력.
• 흐름:
  • h, w 입력.
  • 각 행을 이진수로 변환 (int(input(), 2)).

2. DP 테이블 초기화

• 역할: 초기 행 상태 설정.
• 흐름:
  • dp[j][bit]: 열 상태가 bit일 때 j번 뒤집은 행 수.
  • 초기: 각 행의 비트 패턴으로 dp[0][bit] 채움.

3. 열 뒤집기 반영

• 역할: 열 상태 전이.
• 흐름:
  • i번째 열 뒤집기: bit ^ (1 << i).
  • j번 뒤집은 상태에서 j+1번으로 전이.

4. 최소 1 개수 계산

• 역할: 최종 결과 도출.
• 흐름:
  • 각 bit 상태에서:
    • i: 뒤집은 열 수 (1의 개수).
    • min(i, w-i): 행별 최소 1 개수.
    • total: 모든 행의 최소 1 합.
  • ans 갱신.

시간복잡도

• 초기화: O(h) (행 비트 변환).
• DP 전이:
  • 열: O(w).
  • 상태: O(2^w).
  • 뒤집기 수: O(w).
  • 총합: O(w^2 * 2^w) (w ≤ 18 → 약 10^6).
• 최소값 계산: O(w * 2^w) (≈ 10^6).
• 총합: O(h + w^2 * 2^w) (h ≤ 2×10^5 → 약 10^6).
• 결과: 2초 내 충분 (10^8 대비 여유).

 

잘한점

• D난이도 문제 풀이
• 등수 상승

아쉬운점

• 문제분석 시간이 많이 걸린다
• 쉬운문제 실수로 제출횟수가 많아졌다

 

 

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