2021년 1월 19일 PS 일지

코포 참여합니다~

codeforces.com/blog/entry/86882

Codeforces Round #696 (Div. 2) - Codeforces

 

A: 관찰이 조금 늦어서 큰일났다는 생각을 했다.

a와 b를 bit sum 한 다음 d를 만드는데

비트 1과 1을 더하면 10이 되는게 아니라 2가 된다.

ex) 110 + 110 -> 220

그런데 연속된 값이 있으면 20 이렇게 자릿수가 줄어든다.

 

b가 주어질 때 a+b의 최댓값을 찾기. (a와 b의 자릿수는 정해져 있음)

앞자릿수가 가장 크고, 자릿수가 안 줄어든게 이득.

그런 경우는 딱 한가지 밖에 없다.

맨 앞자릿수를 1로 고정시키고 다음 자릿수로 넘어갈 때 인접한 비트의 합이 안 같은 경우로 고른다. 두가지 선택지가 있으므로 그 중 하나는 자릿수를 유지시킨다. 둘다 유지시켠 그 중 큰거 하면 됨.

 

B: N이 4개 이상의 약수를 가지고, 최솟값을 가지려면 pq 또는 p^3 꼴

p^3꼴의 경우 p-1>=d 여야 함. 기본 ans를 (d+1)^3으로 박음.

p-1 >=d , q-p >=d를 만족해야 하므로

d+1 이상의 최소의 소수 p를 찾고, p+d 이상의 최소의 소수 q를 찾자.

이때 미리 에라토스테네스의 체로 전처리 해놓으면 소수 판별을 O(1)에 할 수 있다.

 

C:

codeforces.com/blog/entry/86882?#comment-750329

Here comes the key observation. let max(array) = M.

1. M should consist in the first pair. if we don't choose the biggest element, (next 'x') <= M,
   since all elements are positive, we can't eliminate M since M+1 > x

2. If the first pair is chosen, choosing the rest automatically completes. Let's choose the first pair arbitrary. Eliminate the pair from the array. Then the next 'x' is M. by 1., we should choose the biggest element from the remaining array. But this time we know the sum of the pairs. Now, the pair automatically completes since we know one element and the sum of two elements.

After choosing the first pair by brute force, we can complete all the steps in N log N using multiset. The number of possible 'first pair' is N-1. So we can complete the algorithm in O(N^2 log N).

 

D: 대회 중에 못 풀었다.

댓글 보고 AC 띄웟다.

i번째와 i+1번째를 교환했을 때

1...i-1 번째에는 전혀 영향이 없다는 생각을 했는데 거기서 더 발전시키지 못했다.

잘하자 ㅋㅋ

dp라는 생각을 전혀 못함. 양쪽에서 dp 값을 비교한다는 발상이 정말 중요하다.

 

업솔빙 목록

 

E

Problem - E - Codeforces

F

Problem - F - Codeforces