[Codeforces] Round #668

문제 바로가기 : https://codeforces.com/contest/1405
문제 설명은 위 링크에서 확인해주시길 바랍니다.

A solution

길이가 n인 배열은 1~n을 원소로 가지며 각 개수는 1개이다.
배열 p가 input으로 들어왔을 때 p 원소들의 이웃 합을 정렬해놓은 값과 같은 배열 p'을 구해야 한다. (단, p_i != p’_i)
어차피 p' 원소 이웃 합들을 정렬한 값이 p와 같으면 되므로 배열 p를 뒤집으면 된다.

B solution

모든 원소의 합이 0이 되는 배열이 input으로 들어온다.
i<j일 때 a_i-1, a_j+1는 cost가 없으며, 반대 조건에서는 cost가 1씩 발생한다.
모든 원소를 0으로 만들 때 발생하는 최소 cost를 출력해야 한다.

연산을 하더라도 한쪽에는 -1이, 한쪽에는 +1이 되기 때문에 모든 원소 합이 0이라는 사실은 변하지 않는다.
연산 횟수가 최소가 되려면 당연히 i<j일 때 연산을 최대한 해줘야 하는데, 이걸 일일이 반영해주면 TLE를 받는다!
연산을 해가면서 값을 찾아 갈 필요는 없고 앞에서 부터 값을 더해 나가는데 0보다 작을 때는 버리면 된다. O(n)만에 구할 수 있다.
더해 나가면서 0보다 크다면 값이 오르락 내리락 하는데 양수, 음수를 순차적으로 만나 상쇄됨을 의미한다. 이땐 cost가 0이다.
그리고 0보다 작아지는 부분을 거치면 값이 변동되지 않고 쌓이는 경우가 생기는데 이렇게 마지막까지 쌓인 값은 최종 cost가 된다.

나름 규칙을 찾아서 꽤 빨리 풀어냈는데 처음으로 Hack을 당해버렸다. 진짜 멘붕왔다ㅠㅠ

C solution

0, 1, ?로 이루어진 문자열이 주어진다. 그리고 값 k도 주어진다.
길이가 k이고 0과 1이 각각 k/2개인 부분 문자열을 k-balanced라 정의한다. ?는 0 또는 1이 될 수 있다.
이 때, 주어진 문자열이 k-balanced가 될 수 있다면 YES를, 아니면 NO를 출력하라.

길이가 n인 문자열 array가 주어졌고 [0, k-1]인 부분 문자열 a가 있다고 하자. (k < n)
이 때 [k, 2k-1]인 부분 문자열 b가 있다면 (k-balanced가 존재할 때) a[0], b[0]은 같아야 한다.
따라서 이 부분을 다음과 같이 구현해준다.

for (int j = i; j < n; j += k) {
	if (s[j] != '?') {
		if (tmp != -1 && tmp != s[j] - '0') {
			ret = false;
			break;
		}
		tmp = s[j] - '0';
	}
}

연속된 부분 문자열은 원소를 공유하기 때문에 모든 케이스의 부분 문자열을 탐색할 필요가 없다.
따라서 [0, k-1]까지만 탐색하고, 각 인덱스에서 위의 for loop를 돌면 된다.
내부 for loop를 돈 후에는 (ret이 아직 true라면) 현재 원소가 ?가 아닐 때 0 또는 1의 갯수를 카운트해준다.
카운트된 0, 1의 갯수는 [0, k-1]에서 탐색한 결과다. 0, 1 중 큰 값을 택해 k/2보다 크다면 ret을 false로 바꿔준다.
max(zero, one)은 k/2보다 작거나 같을 수 있다. [0, k-1]에 ?가 포함될 수 있기 때문에 그렇다.

if (max(zero, one) > k/2) {
			ret = false;
		}

//output
if(ret) cout << "YES" << '\n';
else cout << "NO" << '\n';

C는 이리저리 끄적이다가 코드가 100줄이 넘어가면서.. 이건 아니다 싶어서 결국 풀지 못했다.
공부해보자는 생각에 왜 이렇게 동작해야 답을 구할 수 있는지 천천히 따라가 봤는데 참 놀랍고 대단한거 같다.
아무렇지도 않게 3솔 이상을 하는 사람들이 많이 보여서 부럽다. 언제쯤 합류할 수 있을까🤔