Codeforces Round #624 (Div. 3) 후기

Codeforces Round #624 (Div. 3)

Dashboard - Codeforces Round #624 (Div. 3) - Codeforces

A. Add Odd or Subtract Even

처음에 정수 $a$와 $b$가 입력으로 들어오고 $a$에 홀수를 더하거나, 짝수를 빼는 연산을 해서 $b$를 만드는 문제였다.

 

그럼 단 다섯 가지 경우만 생각하면 되는데.

    1. $a<b$이고 $|b-a|$가 홀수인 경우

    2. $a<b$이고 $|b-a|$가 짝수인 경우

    3. $a>b$이고 $|b-a|$가 홀수인 경우

    4. $a>b$이고 $|b-a|$가 짝수인 경우

    5. $a=b$인 경우

 

각 경우에 따라 차 만큼 더해주거나 빼고, 홀수 짝수를 판별해 1을 추가로 더하거나 빼주는 과정을 반복한다면 반드시 2회 안에 모든 $a$를 $b$로 만들 수 있다.

 

B. WeirdSort

정렬은 정렬이지만, 특수한 규칙이 있는 정렬을 한 다음, 정렬 된 수열이 오름차순인가 아닌가를 판별하는 문제이다.

특별한 규칙이란, $[p_1, p_2, ... , p_m] (0<m<n)$이라는 수열이 주어졌을 때, $p_i$가 수열 안에 있다는 의미는 배열의 $i$번째와 $i+1$번째 원소를 서로 교환할 수 있다는 뜻이다.

 

처음엔 옛날 Google Codejam에 나온 홀수자리 짝수자리 문제만 생각해서 자리를 바꿀 수 있는 모든 위치를 체크해 그 위치의 숫자들 전체를 정렬하고 원래 배열에 삽입했더니 Testcase 2번에서 WA를 받았다. 곰곰히 생각해보니 $p_i$가 주어지더라도 바꿀 수 있는 위치는 $p_i$와 $p_{i+1}$뿐이지 $i+23$번째 원소와는 자리를 바꿀 수 없는 것이다!

 

따라서, $p_{i+1}-p_i > 1$이 될 때 까지 Swap 가능한 구간을 연결한 다음 그때그때 부분부분 정렬만 해주면 된다.

그 후, 오름차순인지 아닌지만 판단하면 되기 때문에 $O(tnlogn)$에 문제를 풀 수 있다.

 

C. Perform the Combo

문자열 $S$가 주어질 때, 문자열의 첫 번째 문자부터 마지막 문자까지 연속으로 누르는 것을 Combo라고 한다고 한다.

이 때, 반드시 $m$회의 실수가 발생하며 놀랍게도 $m$회의 실수를 할 때 각각 몇 번째 버튼에서 실수하는지 알 수 있다고 한다. ($p_i$번째에서 실수를 한다 <=> $p_i$번째 버튼까지 누르고 처음부터 다시 시작한다)

 

최대 문자열의 길이가 $|S|$가 20만이므로, 처음부터 일일히 세주면 $O((20*10^5)^2)$의 시간복잡도가 걸리므로 절대 해결할 수 없다.

 

이런 경우 부분합을 이용하면 구간 $[l, r]$에서 등장하는 각 알파벳의 개수 계산을 $O(1)$에 할 수 있다.

string s;
vector< vector<ll> > dp(n, vector<ll>(26, 0));
dp[0][s[0] - 'a']++;
for (ll  i = 1; i < s.length(); i++) {
	for (ll j = 0; j < 26; j++) {
		dp[i][j] = dp[i - 1][j];
	}
	dp[i][s[i] - 'a']++;
}

이렇게 전처리를 해서 prefix sum을 구해 준 다음 들어오는 $m$개의 숫자에 대해 알파벳의 개수를 계속 더해주면 된다. 최대20만 짜리가 20만번 더해질 수 있으므로 long long자료형을 사용하도록 했다. (문제엔 제약조건이 있다고 했지만 실제 채점 데이터에는 버그가 있었다고 한다.)

 

이렇게 풀면 $O(t(n + m))$에 문제를 해결할 수 있다.

 

참고로 최대 문자열 길이가 20만이라고 해서 전역변수로 $dp[200000][26]$배열을 선언한 다음, 매 테스트 케이스마다 초기화를 하게되면 TLE를 받는다.

왜냐하면 초기화 시간이 $O(200000*26*t)$인데 $t$가 100이므로 $O(520,000,000)$이기 때문이다.

D. Three Integers

1 이상 10,000이하 정수 $A, B, C$가 주어졌을 때, 각 정수에 +1 혹은 -1 하는 연산을 몇 번이든 할 수 있다고 한다. 이 때 $A|B$, $B|C$를 만족하게 할 수 있는 최소한의 연산 횟수와 $A', B', C'$를 출력하는 문제이다.

 

정해는 $0<a<2A+1$의 범위에서 $0<b<2B+1$의 범위에서, $C$를 정해주면 되는 것이라는데, 그럴싸 했다.

 

여담으로 $B$를 고정시킨 뒤 greedy하게 접근한다는 방법도 있는데 아마 뚫리는 것 같다.

 

총평

음.. D가 좀맘에 안드는데 E나 F도 펜윅트리나 세그먼트 트리를 사용한 문제였는데 블루 미만이 과연 저러한 자료구조를 사용할 수 있었을까..? ABC | D |||||| EF 정도 난이도로 볼 수 있겠다.