Educational Codeforces Round 131

총평

재밌는 라운드였다. 2시간 거의 꽉 채워서 풀어본 라운드가 흔치 않은데, 시간을 알차게 쓸 수 있었다. 좀만 덜 틀렸으면 더 좋았을 텐데.. 그래도 조금씩 나아지고 있는 것 같긴 하다.

대회 후기

(등수는 open hacking phase 끝나면 올릴 예정)

A는 그냥 개쉬운 문제였다. 오만하게도 제출창 Python 코딩을 시도했는데 Compilation Error -> 예제 WA를 거쳐 맞을 수 있었다. (지문 잘못 읽었음)

B도 쉽길래 또 제출창 코딩을 시전했는데 이번엔 다행히 맞았다.

C는 Parametric Search를 써야 하길래 아쉽게도(?) C++로 코딩을 했다. 어렵지 않게 한 번에 맞았다.

D는 처음에 이상한 생각을 해서 코드를 짜기까지 한 다음 예제가 안 나오는 걸 보고 틀린 걸 깨달았다. 그리고 나서 바로 올바른 풀이가 생각나서 짰다. 오늘의 아쉬움 포인트 1.

E를 봤는데 뭔가 풀이가 구체화가 될 듯 말 듯 어려웠다. 좀 고민하다가 F도 보기로 했다.

F는 뭔가 문제가 상당히 짧았는데, 간단한 O(NQ) 풀이가 존재하는데 시간 제한이 뭔가 애매하게 길게 설정이 되어 있었다. 그래서 naive + #pragma의 유혹에 빠져서 냈다가 TLE를 받고 (ㅋㅋ) 코드를 다시 보니 그냥 자료구조를 써서 최적화를 하면 되는 거 같이 생겼다. 처음에 lazy segtree를 열심히 짜다가 뭔가 잘 안 되는 것 같아서 bucket(sqrt decomposition)으로 다시 짜서 냈더니 이번엔 맞았다. (* 끝나고 보니까 그냥 lazy seg로도 할 수 있었음) 오늘의 아쉬움 포인트 2.

그리고 나서 E를 다시 찬찬히 생각하니 이번에는 풀이가 정리가 되었다. 그런데 각종 코너케이스 부분에서 실수를 많이 해서 좀 많이 틀렸다. 오늘의 아쉬움 포인트 3.

문제별 풀이

A

네 칸이 다 1이면 2, 다 0이면 0, 아니면 1이 답이다.

코드 : https://codeforces.com/contest/1701/submission/163216837

B

순열에서 p[i+1] = d * p[i]인 위치를 최대한 많이 만들어야 한다. 우선, 1, 2, ..., n 중에서 d배 차이나는 두 수의 쌍은 (1, d)부터 ([n/d], [n/d]*d) 까지 정확히 [n/d]개 있으므로 d=2인 경우가 가장 좋음을 알 수 있다.

이제 [n/2]개의 모든 쌍이 순열에서 다 나타나도록 해야 하는데, 이것은 그냥 1 2 4 8 ... 3 6 12 ... 5 10 ... 이런 식으로 각 홀수마다 n을 넘지 않을 때까지 2배씩 해서 붙여주면 됨을 알 수 있다.

코드 : https://codeforces.com/contest/1701/submission/163306571

C

Parametric search를 하자. 즉, 어떤 K를 고정해 K분 이내에 모든 작업을 끝낼 수 있는지 판별해 보자.

우선 자신의 전문 작업이 있다면 할 수 있는 한 최대로 하는 것이 좋다. 한 사람이 최대 K개씩 할 수 있고, 그렇게 배분하고 나서도 남는 작업은 여력이 되는 사람이 또 나눠서 해야 한다. 이 때, 어떤 사람이 자기 전문 작업을 C개 했다면 남는 작업을 [(K-C)/2]개 더 할 수 있다. 그렇게 모든 작업을 나눌 수 있다면 가능 / 아니면 불가능.

코드를 너무 대충 짜면 overflow가 날 수도 있으니 주의할 것.

코드 : https://codeforces.com/contest/1701/submission/163229041

D

각 위치마다 \( b_i = \lfloor \frac{i}{a_i} \rfloor \) 를 만족하기 위한 \( a_i \)는 구간으로 나타난다. \( b_i \le \frac{i}{a_i} < b_i + 1 \) 라는 식을 \( a_i \)에 관해 풀면 \( \frac{i}{b_i + 1} < a_i \le \frac{i}{b_i} \), 즉 \( a_i \)가 정수이므로 \( \lfloor \frac{i}{b_i + 1} \rfloor + 1 \le a_i \le \lfloor \frac{i}{b_i} \rfloor \) (단, \( b_i = 0 \)일 경우 \( \frac{i}{b_i} \) 대신 \( n \)) 이라는 구간을 얻게 된다.

이제 1부터 n까지의 각 정수를 구간 n개에 하나씩 대응시키면 되는데, 이는 매우 전형적인 스케줄링 문제이므로 매우 다양한 그리디로 풀 수 있다. 대충 생각나는 대로 deadline first를 짜면 된다.

- 1부터 n까지 수를 하나씩 보면서 자신이 들어갈 수 있는 구간 중에 끝점이 가장 작은 구간에 매칭
- 구간을 끝점이 작은 것부터 하나씩 보면서 남아있는 수 중에 가능한 가장 작은 수를 배당 (내가 짠 방식)

답이 무조건 있는 입력만 주어지므로 불가능한지 처리는 신경쓰지 않아도 된다.

코드 : https://codeforces.com/contest/1701/submission/163245112

E

일단, s에서 t가 subsequence(부분순서)로 등장해야만 변환 가능함은 쉽게 알 수 있다. s를 건드릴 수 있는 방법이 s의 문자를 지우는 것밖에 없기 때문이다.

그 다음으로 관찰할 사실은, 최적의 키 입력은 아래의 두 Case 중 하나라는 것이다.

(1) 뒤에서부터 문자열을 훑으면서 지울 글자 앞에선 backspace, 안 지울 글자 앞에서는 left를 누른다. 지워야 할 글자를 다 지우면 끝낸다.
(2) (1)의 행동을 어느 시점까지 하다가 Home 키를 딱 한 번 누른다. 그 다음 앞에서부터 문자열을 훑으면서 글자를 안 지울 거면 right, 지울 거면 right -> backspace를 누른다. 역시 지울 글자를 다 지우면 끝낸다.

Home 키는 많아야 1번, End 키는 많아야 0번 누르면 된다는 사실을 기반으로 정리를 해 보면 알 수 있다.

s와 t는 각각 길이 n, m의 0-based 배열로 생각하자. lcp[i][j] : s[i..]와 t[j..]의 최대 공통 접두어 (longest common prefix) 로 정의하자. 참고로 lcp 배열은 간단한 dp로 O(nm)에 계산할 수 있다.

Home 키를 누르지 않을 경우의 답은 n - lcp[0][0]이다. 앞에서부터 그리디하게 s - t 매칭을 구하다가 처음으로 안 되는 시점에서부터 s의 글자를 지워야 하기 때문이다.

Home 키를 누르는 경우의 답을 구하기 위해서는 다음과 같은 O(nm)개의 케이스를 고려하면 된다.

- s[i]를 t[j]에 매칭시킨다. 그 앞에서 지울 글자는 Home 버튼을 누른 뒤 앞에서부터 지우고, 그 뒤에서 지울 글자는 처음에 뒤에서부터 오면서 지운다.

(참고로 여기서 s[i-1]은 무조건 지워진다고 가정한다. 만약 s[i-1]을 안 지워도 된다면 i와 j를 각각 하나씩 감소시킨 경우에서 고려를 하므로 상관이 없음)

이렇게 지우는 것이 가능하려면 우선 s[i] == t[j]가 성립해야 하고, s[..i-1]과 t[..j-1], s[i+1..]과 t[j+1..]이 각각 매칭 가능해야 한다. 매칭 가능한지에 대한 판별은 다음의 두 배열 pf[]와 sf[]를 O(n+m)에 각각 구해 놓으면 O(1)에 가능하다.

pf[j] : t를 앞에서부터 s와 매칭시켰을 때, t[j]가 매칭되는 s[i]에 해당하는 i 값
sf[j] : t를 뒤에서부터 s와 매칭시켰을 때, (...)  i 값

이 때의 답은 (n - i - lcp[i][j]) + 1 + (i + (i-j))이다. 각각 뒤에서부터 지우고 오는 연산 / Home button / 앞에서부터 지우는 연산에 대한 비용이다.

풀이를 깔끔하게 정리해내는 것이 상당히 어려운 문제인 듯 하다. 코딩 할 때도 코너 케이스를 잘 따져 주어야 한다. 대회 때 짠 코드는 케이스 분류가 뭔가 이상해서 약간 다듬어서 공개한다.

코드 : https://codeforces.com/contest/1701/submission/163310169

F

다음의 두 배열 C, H를 정의하자.

C[i] : 현재 set에 있는 i < k <= i+d 인 k의 개수
H[i] : 지금 set에 i가 있으면 1, 없으면 0

각 쿼리마다 구해야 하는 값은 \( \sum_{x=1}^{200,000}{H[x] * C[x](C[x]-1)/2} \) 이다. 답을 ans라는 변수 하나에 담아 계속 관리한다고 하자. 편의상 2를 곱해서 구하고 출력할 때는 다시 2로 나눈다고 하자.

set에 원소가 추가/제거될 때 C[i], H[i]와 ans는 각각 아래와 같이 바뀐다.

x 추가 : x-d <= i < x인 각각의 i에 대해 ans += 2 * H[i] * (C[i]++); 이후 ans += C[x] * (C[x] - 1); H[x] = 1;
x 제거 : x-d <= i < x인 각각의 i에 대해 ans += 2 * H[i] * (--C[i]); 이후 ans -= C[x] * (C[x] - 1); H[x] = 0;

이것을 자료구조로 최적화하려면, 다음의 일을 빠르게 해 주어야 한다.

- C의 구간에 일정한 수 더하기
- 구간에서 (H[i] * C[i])의 합 구하기
- 특정 점의 C[x] 구하기
- 특정 점의 H[x] 변경하기

Sqrt decomposition으로 문제를 접근하자. 1부터 20만까지를 대충 루트 단위로 Bucket으로 나누고, Bucket 전체에 구간 연산을 지원하는 것을 빠르게 해 주면 된다. 이를 위해서는 각 Bucket마다 C, H 배열과 더불어 아래의 세 변수를 추가로 저장하면 된다.

- ofs : Bucket의 C[i] 전체에 더해진 값
- has : Bucket에서 H[i] = 1인 i의 개수
- tot : H[i] * (C[i] + ofs) 값의 합

코드 : https://codeforces.com/contest/1701/submission/163281192