codeforces R702 D3

solved: 2 out of 7

 

A,B 삽질해서 2문제 푸는데 30분 걸렸습니다.

C번은 전처리해서 배열로 만들기는 했는데 이후 접근법에 있어 투포인터를 사용하는 트롤링, 그대로 2솔하고 끝나버렸습니다.😭

투포인터가 N개 배열에서 가능한 두개를 모두 탐색하는게 아니라는 점을 계속 잊고 있는 것 같습니다.

 

A. Dense Array

문제에서 친절하게 식을 줘서 그대로 구현하면 됩니다.

$\frac{max\left ( a_{i}, a_{i+1} \right )}{min\left ( a_{i}, a_{i+1} \right )} > 2$ 인 경우 원소를 몇개 넣어야 하는지 카운팅해주면 해결 할 수 있습니다.

저는 이 부분을 구현하는데 시간을 소모했는데 어렵지는 않습니다 아래와 같이 쉽게 구현 할 수 있습니다.

            if (MX>2*mx) {
                while (MX>mx) {
                    mx=mx*2;
                    cnt++;
                }
                cnt--; // 한번 더 세져서 다 세고 이후에 한번 빼줍니다
            }

 

B. Balanced Remainders

결국 $c_{0}=c_{1}=c_{2}=k, k=n/3$ 이를 구현하면 문제를 해결 할 수 있습니다.

chk[i] := 나머지가 i인 원소의 갯수

위와 같이 배열을 정의하고 카운팅하다가 k보다 커지면 원소에 1을 더해 갯수를 다시 세주었습니다.

다만 이때 1을 더해줘도 k이상인 경우 한번 더 반복해주었습니다.(나머지가 결국 3개 뿐이라 이렇게 if문 2번을 써줍니다)

        if (chk[tmp%3]>k) {
                ans++;
                chk[tmp%3]--;
                chk[(tmp+1)%3]++;
                if (chk[(tmp+1)%3]>k) {
                    ans++;
                    chk[(tmp+1)%3]--;
                    chk[(tmp+2)%3]++;
                }
            }

 

C. Sum of Cubes

최악의 경우 b가 0일때 a는 $10^4$입니다.

따라서 1부터 $10^4$까지 p[i] := $i^3$ 이렇게 정의합니다.

모든 a에 대해 $b^3 = x - a^3$임으로 1부터 $10^4$까지 이를 만족하는 b가 있는지 찾아주면 됩니다.

이때 $O\left ( N^2 \right )$이 걸리는데 b를 이분 탐색으로 찾아주면 $O\left ( NlogN \right )$안에 해결 가능합니다.

    for (int i = 1; i < 10001; i++) {
            ll res = x-p[i];
            int lt = 0, rt = 10000;
            while (lt+1<rt) {
                int mid = (lt+rt)/2;
                if (power(mid, 3) > res) rt = mid;
                else if (power(mid, 3) < res) lt=mid;
                else {
                    f = true;
                    break;
                }
            }
            if (f) break;
        }