Codeforces Round 861 (Div. 2) - Playing in a Ca지no 링크
(2023.04.13 기준 Difficulty *1200)

문제

하나의 양수가 적혀 있는 m개의 카드를 가지고 있는 n명의 선수가 있다.
모든 쌍의 선수들은 각 한 번의 경기를 하는데, 승리자는 같은 순서의 카드의 차이의 합만큼의 상금을 얻는다. 이 때, 상금의 총 합을 출력

알고리즘

일일이 구하면 TLE. 수식을 정리해서 한번 살펴보자.

풀이

일단, 각 열은 독립적임을 알아야 한다. 어차피 상금의 총 합이므로 각 열마다의 카드 번호 차이를 계산하면 되는 것이다.

첫번째 예제의 첫 번째 열은 [1, 7, 3]. 차이는 곧, 구간이라고 생각할 수 있다. 1~7 구간은?
1~3 구간과 7~3 구간의 합과 같다. 어.. 뭔가 정렬하면 될 것 같지 않은가?
정렬하면 [1, 3, 7]. 총 상금은 (3 - 1) + (7 - 1) + (7 - 3) 이다. 규칙성이 보이지 않는가? 1은 빼기로 2번 나온다. 3은 더하기 1번, 빼기 1번. 7은 더하기 2번. 즉, 정렬한 뒤에 각 수를 [-2, 0, 2] 만큼 곱해서 더해주면 된다.
두번째 예제의 첫 번째 열을 정렬하면 [1, 1, 3, 4]. 첫번째 1을 1.1, 두번째 1을 2.1 이라고 표현해서 총 상금은 (2.1 - 1.1) + (3 - 1.1) + (4 - 1.1) + (3 - 2.1) + (4 - 2.1) + (4 - 3). 1.1은 빼기 3번, 2.1은 더하기 1번, 빼기 2번, 3은 더하기 2번 빼기 1번, 4는 더하기 3번. 즉, 정렬한 뒤에 각 수를 [-3, -1, 1, 3] 만큼 곱해서 더하면 된다.

n = 3일 때는 [-2, 0, 2]. n = 4일 때는 [-3, -1, 1, 3]. 규칙은 2가지.
1. 1 - n부터 시작
2. 2씩 증가

이를 이용해 각 열을 정렬 후 순서에 알맞게 곱해서 다 더하면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, m, c;
ll times, result;
vector<int> cards[300000];
 
void solve(){
    cin >> n >> m;
    for (int i = 0; i < m; i++) cards[i].clear();

    // 각 열을 분리해서 입력 받자.
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> c, cards[j].push_back(c);
 
    // 선수가 1명이면 0 출력
    if (n == 1){
        cout << 0 << '\n';
        return;
    }
 
    result = 0;
    for (int i = 0; i < m; i++){
        sort(cards[i].begin(), cards[i].end()); // 각 열을 정렬
        times = 1 - n; // 곱해주는 수는 1-n부터 시작
        for (int j = 0; j < n; j++) result += cards[i][j] * times, times += 2; // 곱해주는 수는 2씩 증가
    }
    cout << result << '\n';
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int t;
    cin >> t;
    while (t--) solve();
}

• Python

import sys; input = sys.stdin.readline
 
for _ in range(int(input())):
    n, m = map(int, input().split())

    # 행렬을 입력받아 행과 열을 뒤집자.
    matrix = list(map(list, zip(*[list(map(int, input().split())) for _ in range(n)])))
 
    # 선수가 1명이면 0 출력
    if n == 1:
        print(0)
        continue
 
    result = 0
    for i in range(m):
        matrix[i].sort() # 각 열을 정렬
        times = 1 - n # 곱해주는 수는 1-n부터 시작
        for j in range(n):
            result += matrix[i][j] * times
            times += 2 # 곱해주는 수는 2씩 증가
    print(result)

여담

제목이 이상할 수 있다.
velog 자동 필터링 때문에 계속 비공개로 올라가서 저렇게 적을 수 밖에 없었다.. 또르르