Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2) , 1397 -> 1482 (+85)

http://codeforces.com/contest/1556

Dashboard - Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2) - Codeforces

 

 

!!!! 모든 답은 제 풀이일 뿐 정해가 아닐 수 있습니다 !!!!

 

 

A. A Variety of Operations

http://codeforces.com/contest/1556/problem/A

Problem - A - Codeforces

 

문제

 

두 개의 수 A, B에 대하여 ( 시작은 A = 0, B = 0)
에서부터 시작하여 임의로 양의 정수 K를 고른 뒤,

1. 양쪽 수에 K를 더하거나
2. A에 K를 더하고 ,  B에 K를 빼거나
3. A에 K를 빼고, B에 K를 더한다.

입력 값이 주어지면 한 번에 하나의 기능을 이용해 최소 기능의 수를 출력하는 문제

 

풀이

 

입력 값이 주어지면 

1. 두 입력 값이 0이다 -> 답은 0

2. 두 입력 값이 0이 아니지만 같다 -> 답은 1

3. 두 입력 값이 다르다

• 두 입력값 차이의 절댓값이 짝수다 -> (ex 8 10) , 9 9로 맞춘 다음 1씩 더하고 빼주면 되기 때문에 답은 2
• 두 입력값 차이의 절댓값이 홀수다 -> 답은 -1

코드

 

#include <bits/stdc++.h>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		long long a, b;
		cin >> a >> b;
		if (a > b)swap(a, b);
		if (a == 0 && b == 0) {
			cout << 0 << '\n';
			continue;
		}
		if (a == b) {
			cout << 1 << '\n';
			continue;
		}
		long long dif = b - a;
		if (dif % 2) {
			cout << -1 << '\n';
		}
		else {
			cout << 2 << '\n';
		}
	}
}

 

B. Take Your Places!

http://codeforces.com/contest/1556/problem/B

Problem - B - Codeforces

문제

 

n개의 수가 있는 배열이 주어졌을 때, 인접해있는 수들끼리 짝수나 홀수가 달라야 한다.

이때 원래 배열의 원소에서, 양옆으로 옮길 수 있는데 조건에 맞게 배열을 바꾸려면 최소 몇 회를 움직여야 하는가?

 

 

풀이

 

우선 배열의 원소들을 짝수면 0, 홀수면 1로 바꾼다

이후 배열 길이에 맞게 2가지 경우의 수 중 최소 값을 출력한다

• 0101010 (0으로 시작하는 배열)
• 1010101 (1로 시작하는 배열)

로 바꾸었을 때 드는 비용 중 최소 값을 출력한다.

여기서 기존의 배열이 0001111이라고 가정하였을 때 

0을 옮기는 이동의 수나 1을 옮기는 이동의 수나 답은 똑같다.

본인은 1을 옮기는 수로 최소 값을 구하였다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
int a[100001];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
 
	while (T--) {
		int n, even = 0, odd = 0;
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> a[i];
			a[i] = a[i] % 2;
			if (a[i])odd++;
			else even++;
		}
		if (n == 1) {
			cout << 0 << '\n';
			continue;
		}
		int dif = abs(even - odd);
		if (dif > 1) {
			cout << -1 << '\n';
			continue;
		}
		long long ans = INT64_MAX;
		long long start = 1,tans=0;
		int temp0 = n / 2, temp1 = n / 2;
		if (n % 2)temp0++;
		if (temp0 == even && temp1 == odd) {
			for (long long i = 0; i < n; i++) {
				if (a[i]) {
					tans += abs(i - start);
					start += 2;
				}
			}
			ans = min(ans, tans);
			tans = 0;
		}
		start = 0;
		temp0 = n / 2; temp1 = n / 2;
		if (n % 2)temp1++;
		if (temp0 == even && temp1 == odd) {
			for (long long i = 0; i < n; i++) {
				if (a[i]) {
					tans += abs(i - start);
					start += 2;
				}
			}
			ans = min(ans, tans);
		}
		cout << ans << '\n';
	}
}

C. Compressed Bracket Sequence

http://codeforces.com/contest/1556/problem/C

Problem - C - Codeforces

문제

n개의 수가 주어졌을 때 , ( i = 1~n )  (i가 홀수면 '('의 개수, i가 짝수면 ')'의 개수)

올바른 괄호 쌍의 개수를 찾는 문제

ex) 
4
2 2 1 1

( ( ) ) ( )

ans = 4 

( ), ( ( ) ) , ( ), ( ( ) ) ( ) 

 

풀이

올바른 괄호 쌍을 '덩어리'라고 부를 때, 현재 인덱스 괄호 쌍 + 이전 덩어리들을 더해주면 된다.

D [i] = i번째 열까지 왔을 때, 연속된 덩어리의 개수

 

코드

#include <bits/stdc++.h>
using namespace std;
long long a[1001], d[1001];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)cin >> a[i];
	long long ans = 0, start = 0;
	for (int i = 0; i < n; i++) {
		if (i % 2) {
			long long start = a[i];
			for (int j = i - 1; j >= 0; j -= 2) {
				if (start < a[j]) {
					a[j] -= start;
					ans += start;
					start = 0;
					d[i] = 1;
					break;
				}
				else {
					if (a[j] == 0)continue;
					ans += a[j];
					start -= a[j];
					a[j] = 0;
					if (j > 0)ans += d[j - 1];
					if (start == 0) {
						if (j > 0) d[i] = d[j - 1] + 1;
						else d[i] = 1;
						break;
					}
				}
			}
			if (start)d[i] = 0;
		}
	}
	cout << ans << '\n';
}

레이팅 변화 : 

1397 -> 1482 (+85)

 

자세한 설명에 중점을 두기보다는 대회 기록에 중점을 둔 글입니다 !

틀린 부분은 감사히 지적받겠습니다.