[Codeforces Round #953] C - Manhattan Permutations

 

Problem - C - Codeforces

알고리즘 : 그리디, 구현
 

1. 문제요약

• 1부터 n까지 n개의 수를 적당히 배치한 수열을 $p_1,p_2,...,p_n$이라 하자.
• Manhattan value란 $|p_1 - 1| + |p_2 - 2| + ... + | p_n - n|$을 말한다.
• t개의 테스트케이스가 존재한다. 각 테스트케이스마다 n과 k가 주어질때, Manhattan value를 k로 만드는 수열이 존재한다면 'Yes'와 함께 그러한 수열  $p_1,p_2,...,p_n$을 출력한다. 존재하지 않는다면 'No'를 출력한다.
• 예시 입출력은 아래와 같다. 

2. 아이디어

• 우선 수열이 1, 2, ..., n이라면 Manhattan value는 0이된다. 여기서 임의의 두 수의 위치를 바꾸게 되면 Manhattan value의 변화량이 항상 짝수임을 쉽게 알 수 있다. 즉 k가 홀수이면 정답에 해당하는 수열이 존재하지 않는다.
• 이제 Manhattan value의 상한값을 알아야 한다. 직관적으로 n개의 값들이 약 n/2의 값을 가질때 최대가 됨을 파악할 수 있는데, 가장 간단한 예시로는 수열이 n, n-1, ... , 1과 같이 뒤집힌 경우가 있을 것이다. 이를 대입한 값을 $m_n$이라 하자.
• 1, ... n 의 수열에 대하여 $m_{n-1} +2$부터 $m_n$까지의 모든 짝수를 얻을 수 있음을 쉽게 증명할 수 있는데, 여기에 더해 1, 2, ... ,n-1의 수열에 대하여 $m_{n-1}$ 이하의 모든 짝수를 만들 수 있다고 가정하면 귀납적으로 $m_n$이하의 모든 짝수를 만들 수 있음을 알 수 있다.

3. 느낀점

• 코드포스에 입문하여 참여한 첫 라운드였는데 이 c번 문제에서 컷당하였다.
• 위 아이디어까지는 도출하였으나 각 테스트케이스마다 목표값에 이르는 수열을 구현하는 과정이 너무 오래 걸렸던 것이 패인이었다.
• 코드가 장황하게 길어지는 것은 뭔가 잘못되고 있음을 말해주는 신호임을 기억하자

4. 파이썬 코드

t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    tmp = n // 2
    maximum = 2 * tmp * (tmp + n % 2)
    if k % 2 or k > maximum:
        print('No')
        continue
    else:
        print('Yes')
        p = list(range(1,n+1))
        l, r = 0, n-1
        while l < r:
            d = (r - l) * 2
            if d <= k:
                p[l], p[r] = p[r], p[l]
                k -= d
                l += 1
            r -= 1
        print(*p)