[24.02.21] CF Round 922 div. 2 upsolve +

A번은 문제를 잘 읽어봐야 한다. 굳이 N * M 넓이의 wall을 세로 벽돌까지 써서 채워야 할 필요가 없고 가로 벽돌만 채우면 된다.

import sys
input = sys.stdin.readline
 
T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
 
    #가로(M) == K 일 때, 벽돌 N개
    tmp = M//2*N
    print(max(N, tmp))

 

 

B번은 inversion을 최소화하는 문제이다. (i, j) 인덱스 순서쌍이 있고, i < j 인데 arr[i] > arr[j] 인 경우 inversion 상태라고 정의한다. 이 상태를 최소화 시키기 위해서 우리는 A arr, B arr에서 동시에 스왑을 해줘야한다. (i, j) -> (j, i) 이렇게 스왑을 해야하는데, 문제는 두 개의 리스트를 모두 고려해야 하기 때문에 복잡해진다.

나는 처음에 하나씩 그려보면서 어떻게 스왑해야하는지 고민했다. 일단 N/2 을 기준으로 a[i], b[i] 값이 앞에 있으면서 N/2보다 큰 것을, (N/2 기준) 뒤에 있으면서 값이 N/2 보다 작은 a[j]와 b[j] 를 골라 서로 스왑하는건가? 싶어서 시도해봤다.

그러나 친절하게도 예제 1번을 보면

1 2 3 4 5

5 4 3 2 1 

이런 경우에서 절대 움직일수가 없다. 흠... 절대 움직일수가 없다고..?

1번에 대한 답 inversion을 계산해봤더니 처음 상태나 답이나 둘다 10으로 같았다... 한 쪽이 일단 정렬되면 다른 쪽에서만 나오는 inversion 의 합이 무조건 최소가 되는 건가 싶어서 정렬로 때려 맞추기를 해도 되나? 의심을 했다.

결국 증명을 위해 에디토리얼을 봤는데 정렬하는게 맞았고, 한 쪽을 정렬하면 다른 리스트의 inversion의 합이 최소가 될 수 밖에 없는 이유에 대해 이해할 수 있었다.

 

원문은 영어로 되어있는데, 간단하게 한글로 정리해보자.

우리는 i, j 를 서로 스왑해줄건데, 스왑하기 전에 a[i], a[j] 라는 임의의 한 순서쌍에서 inversion이 있을 수도 있고 없을 수도 있다. (0 or 1) 여기에다가 우리는 b[i], b[j] 도 같이 스왑해야하는데, 기존의 이 순서쌍도 inversion을 0 or 1 개 가지고 있을 것이다.

그렇다면 스왑을 진행했을 때 어떻게 될까? 각각 (ai-aj 의 inversion 개수, bi-bj 의 inversion 개수) 라고 하자.

(0, 0) -> (1,1)  총 inverison 개수 0개 to 2개

(1, 0) -> (0, 1)   총 inverison 개수 1개 to 1개

(0, 1) -> (1, 0)  총 inverison 개수 1개 to 1개

(1, 1) -> (0, 0)  총 inverison 개수 2개 to 0개

 

여기서 어떤 i, j를 잡아도 A list와 B list 에서 inversion의 개수가 1이라면 계속 inversion의 수가 더 늘어나지 않고 같다. 이 조건을 가장 쉽게 맞춰줄 수 있는 방법이 A든 B든 둘 중 하나를 기준으로 정렬을 해주는 거다.

그러면 한 쪽 리스트는 이미 정렬되어 있기 때문에 어떤 i, j를 잡아도 inversion이 안나온다. 무조건 반대 리스트에서만 inversion이 나올 수 있고, 각 쌍의 인덱스 i와 j에는 최대 1개의 inversion만 있으므로 두 인덱스의 모든 쌍(a, b)이 교환될 때의 inversion 개수 보다 많아질 수 없다.

 + 이걸 스스로 증명까지 해냈어야 했는데 증명하지 못한게 아쉽다. 그냥 임의의 일반항 ai, aj / bi, bj 에 대해서 서로 순서를 바꾸면 어떻게 될지 차근차근 접근했으면 증명까지 도달할 수 있었을텐데... 아쉬운 마음이 들었다. 

i < j 로 순서가 정해져 있었기 때문에 서로 exchange 했을 때 무슨 일이 일어날지만 보면 된다. 이미 캠프에서 그리디 하면서 배운 내용인데 아직 실전에서 적용이 덜 됐구나 싶었다.

코드는 그냥 정렬하고 출력하면 된다.

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N = int(input())
    ali = list(map(int, input().split()))
    bli = list(map(int, input().split()))
    res = [[0, 0] for _ in range(N)]

    for i in range(N):
        res[i][0] = ali[i]
        res[i][1] = bli[i]

    res.sort()

    for i in range(N):
        print(res[i][0], end = ' ')
    print()
    for i in range(N):
        print(res[i][1], end = ' ')
    print()

 

 

C번은 내게 도전하는 느낌을 줬다. 비트에 대해 배워도 뭔가 직접 코드로 비트 연산을 해보려고 하면 어렵다. 아마 비트 문제를 거의 안풀어봐서 그런 것 같다. 비트마스킹 문제나 dp_bitfield 이런 것도 많이 해봐야한다.

 

---

 

일단 오늘은 신촌 도로망 관리와 쿼리 문제를 꼭 풀 생각이다. https://www.acmicpc.net/problem/31427

31427번: 신촌 도로망 관리와 쿼리

 

그동안 이 문제에 대해서 고민을 너무 많이했다. 씻을 때 5! 를 어떤 방법으로 처리할지 생각하면서 씻었는데 이 방법이 되는지 안되는지를 빨리 코드로 짜봐야 답답함이 풀릴 것 같다.