CF R696 D2

solved 2 out of 6

 

A. Puzzle From the Future

 

문제 태그에는 그리디라고 되어있는데 문제를 풀면서 증명은 생각 못했고 그냥 구현문제처럼 풀었습니다.

문자열 a의 첫 글자는 무조건 1로 시작하고, 그 이후로는 현재 보고있는 인덱스를 i라고 할때 d[i-1]과 a[i]+b[i]의 값을 계속 다르게 해줘서 해결해주면 됩니다.

	rep(i, b.length()) {
            int k = b[i]-'0';
            if (i==0) a+='1';
            else {
                int tmp = (a[i-1]-'0')+(b[i-1]-'0'); // d[i-1]
                if (tmp!=k+1) a+='1';
                else a+='0';
            }
        }

 

B. Different Divisors

 

대회중에 계속 공지가 떠서 특이한 문제였다고 기억이 남습니다.

아무튼 지문에서인지 공지에서인지 모든 divisor를 고려해야한다고 했는데 사실 그럴 필요는 없습니다.

우선 divisor로 1과 지금 보고있는 정수 그 자체는 무조건 포함을 하고, 그 외에 2개 이상의 divisor가 있는지 확인을 해줘야합니다.

예제와 몇가지 테케를 직접 만들어서 쭉 써보면 결국, 수열 P := 1, p, q, pq 를 찾아 문제를 해결 할 수 있다는 결론에 도달할 수 있습니다..(p, q는 어떤 소수)

대회중 저는 d를 1부터 시작해서 3까지 써보고 55를 찾음으로서 이 사실을 확인했습니다.

이를 통해서 문제는 소수를 찾아주고(에라토스테네스의 체 이용) 수열 P를 원소간의 차이가 d이상이게끔 찾아주면 됩니다.

	for (int i=2; i <= 30000; i++) {
            if (ct>=2) break;
            if (isp[i]) {
                if (abs(i-pre)<d) continue;
                ans*=i;
                pre=i;
                ct++;
            }
        }

 

C. Array Destruction

사실 업솔빙을 하긴 했는데 아직 문제를 정확히 이해 못한 부분이 있는 것 같아 나중에 풀이하려고 합니다.