Educational Codeforces Round 161 (Rated for Div. 2)
코포를 꽤나 오랜만에 한 것 같은 느낌.
좀 쉽게 나온 편이긴 한데 아무튼 선방했다. (All solved at 01:05)
A. Tricky Template
간단하게 문제 조건을 만족하는 template을 만들어보면 된다.
세 개의 string a, b, c에 대해서 a[i] != c[i] && b[i] != c[i]인 i가 존재한다면 이러한 template을 만들 수 있다.
B. Forming Triangles
2^x의 특징은 x < y < z라면 무조건 2^x + 2^y < 2^z라는 점이다.
따라서 최소한 두 개의 변은 동일하여야 한다.
1) x가 두 변인 이등변 삼각형의 개수 = C(cnt[x], 2) * (x보다 짧은 선분의 개수)
2) x가 세 변인 정삼각형의 개수 = C(cnt[x], 3)
C. Closest Cities
우선 closest city 자체를 구하는 것은 그냥 양 옆의 도시를 비교하면 되므로 간단하다.
편의를 위해서 쿼리의 x, y가 반드시 x < y 라고 가정하자. (x > y라면 정확히 반대로 하면 된다.)
우리는 평소에 x와 y의 거리를 구한다면 a[y] - a[x] 등의 방법으로 구한다.
하지만 문제에서는 closest로 비용 1로 이동할 수 있으므로, a[y] - a[x]가 아니고, 어떤 다른 b[y] - b[x]인 b를 이용해야 한다.
b를 구하는 것은 쉽다. b[0] = 0이라고 했을 때
1) i - 1번째 도시에서 제일 가까운 도시가 i라면 : b[i] = b[i - 1] + 1
2) 만일 아니라면 : b[i] = b[i - 1] + (a[i] - a[i - 1])
로 정의해주면, b[y] - b[x]를 통해서 답을 구할 수 있다.
D. Berserk Monsters
다양한 구현 방법이 있을 것이다.
핵심은 만일 {A, B, C}의 세 몬스터가 동시에 살아남는다면, 다음 번에도 B는 절대로 죽을 일이 없다.
따라서 처음에는 모든 N개의 몬스터가 죽는지 확인해주어야 하지만,
나머지 N - 1개의 라운드에서는 이전 라운드에 죽은 몬스터 양 옆에 있던 몬스터가 죽는지만 확인해주면 된다.
어차피 몬스터는 한 번밖에 못 죽고, 양 옆에는 최대 2개이니, 3N번 이상 확인할 일은 없다.
E. Increasing Subsequences
{x, y, z}의 sequence가 총 N개의 incresing subsequence를 가졌다고 가정하자.
1) 만일 엄청 작은 숫자가 맨 앞에 붙는다면 : {-1e9, x, y, z}는 2N개의 increasing subsequence를 가진다.
2) 만일 엄청 큰 숫자가 맨 앞에 붙는다면 : {1e9, x, y, z}는 N + 1개의 increasing subsequence를 가진다.
따라서 문제에서 주어지는 X에 대해서 비트에 맞게 숫자들을 잘 추가해주면 된다.
자세한 것은 >>코드참고<<
주의) 애초에 원소가 하나라도 있다면 increasing subsequence는 2개이다.
-> 즉 0부터 시작하는게 아니기에 막무가내로 2배 때리면 안되고, 제일 큰 비트부터 잘 다루어야 한다.
F. Replace on Segment
DP를 하면 된다.
-> YES[L][R][X] : [L, R] 범위에 있는 모든 숫자를 모두 X로 통일 시키기 위해 필요한 비용
-> NO[L][R][X] : [L, R] 범위에 있는 모든 숫자를 X가 아니게 하기 위해 필요한 비용
[L, R]에 X가 없도록 하는 방법은
1) [L, MID], [MID + 1, R] 각자에 X가 없도록 하기.
2) [L, R] 범위 내에 적당히 작업을 친 다음에 문제에서 주어진 Operation로 [L, R]에 X가 아니라 다른 숫자로 바꾸기
등의 방법이 있다.
한 번 WA를 맞았기 때문에 본인은 안전빵으로 덕지덕지 여러 작업들을 붙여두었다 (코드)
정확히 얼만큼 고려해주어야 하는지는 미래에 올라올 editorial 참고