Codeforces Round 951 (Div. 2)

https://codeforces.com/contest/1979

 

제발 안 터지게 해주세요

 

A. Guess the Maximum

 

생각해보면 굳이 많이 차이나는 (i, j)보다는 (i, i + 1)을 뽑는게 Bob에게 항상 이득이다.

따라서 모든 max(a[i], a[i + 1])보다 K가 작으면 되므로 MIN(max(a[i], a[i + 1])) - 1이 답이ㅏㄷ.

 

B. XOR Sequences

 

제일 처음으로 다른 bit를 찾으면 1 << bit이 답이다.

 

C. Earning on Bets

 

총 내가 쓰는 코인의 개수인 Total이 결정되어 있다고 가정하자.

그러면 각 x에는 최소한 Total / k[x] + 1을 배정해주어야 한다.

이때 SUM(Total / k[x] + 1) < Total인 것은 상관없다.

그러면 실제 총합인 real_Total이 총합이 되는데 이게 Total보다 작으면 오히려 이득인 것이다.

만일 반대로 SUM > Total이면 불가능한 것이다.

-> 근데 가능한 Total 값이 있을 수도 있지 않나?

 

이제 제일 이득이 되는 Total을 골라주면 된다.

실제 유리수 Total / k[x]와, 정수인 Total // k[x] + 1 사이의 차이를 최대한 줄여주어야 한다.

이런 Total은 LCM(1, 2, ... 20) - 1을 선택하주는 것이 제일 이득이다.

 

D. Fixing a Binary String

 

미친 깡구현 문제

그냥 그대로 확인을 해보면 된다.

주인장 편의상 0-index로 표현을 하자면 (S[p], S[p + 1], ... S[n - 1], S[p - 1], ... S[0])가 되는지 확인해야 한다.

S[L, x) = (S[L], S[L + 1], ... S[L + x - 1])이라고 하자.

1) S[p, k), S[p + k, k), ... 는 각각 모두 안의 문자들이 동일하고, S[p] != S[p + k] != S[p + 2k] != ...가 성립한다.

-> 이것은 prefix_sum을 이용하여 확인할 수 있다.

2) p = ak + b라고 하면, 중간에 S[n - (k - b), k - b) + S[p - b, b)가 생기게 된다.

-> 이 내부가 우선 모든 원소가 동일해야한다. (마찬가지로 prefix sum)

-> 또한, S[p - b - 1], S[n - (k - b) - 1]과 달라야 한다.

3) S[0, k), S[k, k), ...가 각각 안의 문자들이 동일하고 S[0] != S[k] != S[2k] != ...가 성립한다.

-> 1)과 마찬가지로 prefix_sum으로 할 수 있다.

 

구현 방식에 따라 다르겠지만, 나는 b = 0인 경우, N = K인 경우, p < k인 경우를 예외처리하였다.

 

E. Manhattan Triangle

 

우선 택시거리는 max( (x + y)의 차이, (x - y)의 차이) 임이 알려져 있다.

어떤 세 점이 Manhattan triangle을 이룬다면 다음 조건 중 하나를 만족한다

1) 어떤 두 점의 x + y(= a)값이 동일하고, x - y값은 정확히 d 차이난다(= b, b + d)

-> 이때 나머지 한 점은 x + y가 정확히 d 차이나며 (a - d or a + d), x - y값은 b와 b + d 사이이다.

2) 어떤 두 점의 x - y(= a)값이 동일하고, x + y값은 정확히 d 차이난다(= b, b + d)

-> 이때 나머지 한 점은 x - y가 정확히 d 차이나며 (a - d or a + d), x - y값은 b와 b + d 사이이다.

 

1)의 케이스 중에서 나머지 한 점이 a + d인 경우만 해결하자.

map<int, vector<pii>> plus를 정의하여 plus[x[i] + y[i]].push_back({x[i] - y[i], i})를 해두자.

-> 투 포인터를 이용하여 plus[a]에 있는 모든 x - y 값이 정확히 d 차이나는 쌍을 확인할 수 있다.

-> 또한 투 포인터 비슷하게 plus[a + d]에서 x - y 값이 b 이상이 되는 점을 찾을 수 있다.

-> 이 점의 x - y값이 b + d 이하라면 답으로 가능한 점이고, 아니라면 불가능한 점이다.

이해가 안되면 코드를 참고...

 

F. Kostyanych's Theorem

 

N - 2를 일단 물어보자. 이유는 다음과 같다.

1) 여기서 답으로 나올 수 있는 것은 (A, B) 혹은 (C, 0) 꼴이다

-> 만일 (A, B)가 답이라면 A의 degree가 N - 2임이 보장되며, (C, 0)이 답이면 C의 degree가 N - 1이다.

-> 즉 쿼리에서 degree를 알려주지는 않지만, 대답을 통해 그 점의 차수를 정확하게 알 수 있다.

-> degree가 N - 2 이상인 점이 존재하지 않을 수는 없다 (이러면 간선의 개수가 부족해진다)

2) 만일 degree가 N - 2인 점 A가 삭제된다면, 문제는 그대로 (N -> N - 1)로 바뀐다

-> 즉, 이 점이 삭제된 채로 구한 답에 A를 맨 앞이나 맨 뒤에 붙이면 Hamiltonian이 된다.

-> A는 현재 B를 제외한 모든 점에 연결되어 있으므로 맨 앞이나 맨 뒤에 반드시 붙을 수 있다.

 

(A, B)가 나오면 귀납적으로 답을 구할 수 있다면.... (C, 0)이 나오면 어떻게하나...

-> 이 경우 degree가 N - 2인 점이 없음을 알 수 있다.

-> 그러면 C가 삭제된 경우에는 degree가 N - 3인 점이 없다는 뜻이다!

-> 즉, 이 경우 N - 4를 물어보면 된다.

A) N - 4인 점이 존재한다면

-> 그러면 이번에 N - 4개의 간선을 삭제하게 되고, 이러면 간선의 개수가 정상화되어 N - 2짜리 문제로 볼 수 있다.

-> 이전의 논의와 마찬가지로 귀납적으로 맨 앞이나 맨 뒤에 붙여주면 된다.

B) N - 4인 점이 존재하지 않는다면 

-> 똑같은 논리로 (D, 0)이 대답으로 나와서 삭제되었다고 가정하자

-> 이번에는 degree가 N - 4, N - 5인 점이 없어졌다는 뜻이므로 N - 6을 물어보고, 이런 점이 있다면 정상화되어 귀납

-> 또 없으면 똑같이 N - 8, N - 10, ... 나올 때까지

 

아직 하나의 문제점이 존재하는데, 문제를 정상화 시키는 N - 2K를 물어보았을 때의 답인 (E, F)이다.

E는 degree가 N - 2가 아닌 N - 2K (K  > 1)이기 때문에 실제로 연결이 불가능한 점이 F보다 더 많다.

하지만, E는 무조건 앞의 (C, 0), (D, 0)에서의 C, D와 연결 가능하므로 C - E - D로 E를 이 사이에 삽입하면 된다.

 

마찬가지로 잘 모르겠으면 코드로...