Educational Codeforces Round 131 (Rated for Div. 2)

https://codeforces.com/contest/1701

 

F가 segtree하나 기똥차게 짜면 바로 풀렸을텐데 흠...

 

A. Grass Field

 

보면서 어지간히 낼게 없나 싶었다.

2번이 반드시 필요한지 확인해주면 된다.

 

B. Permutation

 

직관적으로 d = 2일 때가 최선

i, 2i, 4i ... 형태가 되도록 최선을 다해서 배열해주면 된다.

 

C. Schedule Management

 

이분탐색으로 시간을 구할 수 있다.

다만 최대시간이 2m이라는 점에만 유의를 하면 될 것 같다.

 

D. Permutation Restoration

 

각 b[i] 값당 가능한 a[i]의 범위가 [s, e]로 생겨난다.

e로 이들을 정렬하고 배정해줄 수 있는 남은 숫자들의 upper_bound(s)를 배정해주면 된다. (greedy)

pair<int, int>로 정렬을 했지만 생각해보니 결국 a의 값이 정수이기에 대충 나눠도 됐을 것 같다.

 

E. Text Editior

 

당연하게도 end 버튼을 누르는 것은 항상 손해이다.

또한 Home 버튼도 두 번 이상 누르면 손해이다. 

따라서 (맨 뒤) -> (어떤 지점 j) -> home -> (어떤 지점 i)의 방식으로 움직이는 것이 최선이다.

(단, 어떤 지점 i가 0이라면 home 버튼을 누를 필요가 없음에 주의하자.)

만일 저런 행동을 한다면 i부터 j까지는 T와 정확하게 매칭되어야 한다.

1) z function을 알고 있다면 매우 쉽게 할 수 있다. 

2) 굳이 z를 모르더라도 단순한 dp를 통해서 할 수 있다. (공간적인 면에서만 손해를 볼 뿐, 시간복잡도는 같다)

 

F. Points

 

어떤 숫자 a가 삽입될 때 더 생겨나거나 사라지는 triplet의 개수를 세보자.

[a - d, a)에 있는 어떤 숫자 i를 고르자.

이때 [i + 1, i + d] - {a} 에서 임의의 한 숫자 j를 고른다면 (i, a, j) 혹은 (i, j, a)가 생겨남을 알 수 있다.

따라서 sum( [i +1, i + d] - 1) 만큼의 triplet이 a보다 왼쪽에서 생겨난다.

정확히 a가 제일 왼쪽인 triplet의 개수는 [a + 1, a + d]의 원소의 수가 x라면 C(x, 2) 임을 알 수 있다.

-> 따라서 임의의 위치 i에 대해 [i + 1, i + d]에 있는 원소의 수를 관리해주는 자료구조를 만들어주면 된다.

하지만 유의해야하는 것은  sum([i + 1, i + d])에 포함되는 i는 set에 포함된 숫자여야 한다는 것이다.

 

따라서 다음과 같은 segtree를 만들어주면 된다. (물론 다음의 역할을 대체할 수 있는 방식을 채택해도 된다.)

sum(a[i] * b[i])의 출력이 가능하며, a의 구간갱신이 가능하고, b의 점갱신이 가능하다.

lazy를 이용하면 b의 구간갱신까지 가능하도록 설계해줄 수 있다.

https://codeforces.com/contest/1701/submission/163404022

따라서 쿼리마다 새롭게 생겨나거나 사라지는 triple의 개수를 세주면 된다.

 

Editorial) 

 

비슷하게 f(i) = [i + 1, i + d]에 있는 원소의 개수라고 정의한다면, 답은 sum(C(f(i), 2))이다.

-> 따라서 sum(f(i)^2)와 sum(f(i))를 관리할 수 있는 segtree를 만들어주면 된다.

여기서 질문) 그러면 f(i)의 구간갱신을 어떻게 할 수 있는가?

sum((f(i) + 1)^2) = sum(f(i)^2 + 2 * f(i) + 1)이기 때문에 sum(f(i)^2), sum(f(i))를 알고 있다면 쉽게 구할 수 있다.

-> 따라서 matrix를 곱해주는 형태의 segtree를 만들어주면 된다.