[CF] Round #675 (Div. 2) _ 201004

(2020년 10월 21일에 작성한 글입니다.)

 

Dashboard - Codeforces Round #675 (Div. 2) - Codeforces

 

A.

사각형의 네 변 중 세 변 a, b, c가 주어질 때

나머지 한 변의 길이인 d로 가능한것 중 하나를 출력하라는 문제인데

세 변을 더한 것에서 1을 빼는 것도 답이 된다.

근데 이거 처음에 long long 안 해서 한 번 틀렸다...

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	ll a, b, c;

	cin >> T;
	while (T--) {
		cin >> a >> b >> c;
		cout << (a + b + c - 1) << '\n';
	}

	return 0;
}

 

B.

palindrome 형성에 영향을 주는 네 수.

그 네 수를 모두 같도록 만들 때 변화량의 합이 최소가 되게 하면 됨.

예를 들어서 예제에서

1 2 3 4

5 6 7 8

9 10 11 12

​

첫 행이 팰린드롬이 되려면 우선 1, 4를 같게 해야 하고,

첫 열과 마지막 열이 팰린드롬이 되려면 1, 9 / 4, 12가 같아야 하고

마지막 행이 팰린드롬이려면 4, 12가 같아야 한다.

결국 1, 4, 9, 12가 모두 같으면 돼.

그렇게 할 때의 변화량의 합은...

a <= b <= c <= d일 때 c + d - a - b인데

증명은 생략..

이걸 모든 행/열 쌍에 대해 하면 된다.

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	int N, M;
	ll ans;
	int i, j;

	cin >> T;
	while (T--) {
		cin >> N >> M;
		vector<vector<ll>> arr(N, vector<ll>(M));
		for (i = 0; i < N; i++) {
			for (j = 0; j < M; j++) {
				cin >> arr[i][j];
			}
		}

		ans = 0;
		for (i = 0; i < (N + 1) / 2; i++) {
			for (j = 0; j < (M + 1) / 2; j++) {
				vector<ll> temp(4);
				temp[0] = arr[i][j];
				temp[1] = arr[i][M - 1 - j];
				temp[2] = arr[N - i - 1][j];
				temp[3] = arr[N - i - 1][M - 1 - j];
				sort(temp.begin(), temp.end());

				ll num = (temp[1] + temp[2]) / 2;

				ans += abs(arr[i][j] - num);
				arr[i][j] = num;
				ans += abs(arr[i][M - 1 - j] - num);
				arr[i][M - 1 - j] = num;
				ans += abs(arr[N - i - 1][j] - num);
				arr[N - i - 1][j] = num;
				ans += abs(arr[N - i - 1][M - 1 - j] - num);
				arr[N - i - 1][M - 1 - j] = num;
			}
		}

		cout << ans << '\n';
	}

	return 0;
}