CodeForces Round 1011 - Div 2

https://codeforces.com/contest/2085

 

Performance Rating : 3000

 

A

모두 같은 문자로 이루어진 것이 아니라면 한 번만 바꿔서 조건을 만족할 수 있다는 것을 관찰하면서 시작했다. $k=0$인 경우에는 $s$랑 $rev(s)$를 비교하여 답을 출력했고 $k\geq 1$인 경우에는 모든 문자가 같으면 "No", 아니면 "Yes"를 출력했다.

 

B

$0$이 없으면 $1\;n$ 한 번만 해줘도 된다는 것을 관찰하였고, $0$이 하나 있다면 한 번의 수행으로 $0$을 없애준 뒤 한 번의 수행으로 끝내줄 생각을 했다. $0$이 2개 이상일 경우 수열을 $0$이 양 끝에 있다면 수열을 두 부분으로 나누고 아니라면 $0$이 없는 부분을 제외하고 수행을 한번 하여 $0$을 없애준 뒤 한 번의 수행으로 끝내주는 코드를 작성했다.

 

C

 $a+b=a\oplus b$이려면 $a$와 $b$에 겹치는 비트가 없어야 한다는 생각으로 문제를 풀기 시작했다. 일단 $x=y$면 -1을 출력해 주고 둘 중 큰 수를 $2^40$정도로 맞추면 두 수가 같은 비트가 있을 수 없다는 것을 관찰하고 $(1LL<<40)-\mathrm{max}(x,y)$를 출력했다.

 

D

dp로 풀 생각을 해보다가 다른 관찰을 했다. 뒤에서 $(k+1)$개마다 집을 수 있는 접시가 하나씩 추가되는 것을 관찰하고 pq를 쓰면 되겠다는 생각을 했다. 우선 $a$를 뒤집어주고 $sz(pq)$가 $i/(k+1)$이 되도록 $pq$에 원소를 넣고 작은 것부터 빼주는 방식으로 해결했다.

 

E

원소의 최댓값이 $10^6$이라는 것을 보고 각 원소의 개수를 세주고 해싱으로 해결할 생각을 했으나 $t$의 범위가 $10^4$인 것을 보고 포기했다. 30분 정도 생각을 해보다가 $a$, $b$를 정렬해 두고 $a_i-b_i$의 합이 $k$의 배수일 수밖에 없다는 것을 알게 되었다. 각 $i$에 대해 $b_i>a_i$인 경우가 있으면 -1을 출력해 주고, $sum$에 $a_i-b_i$의 값을 모두 더했다. $10^5$까지의 소수를 모두 구해놓고 $sum$의 약수 중에 가능한 것이 있는지 확인하여 가능하면 출력하고 가능한 것이 없다면 -1을 출력하는 방식으로 문제를 해결했다.

 

F1

F1은 $O(nk)$가 충분히 돌아가는 범위이고, F2는 적어도 $O(nlogn)$정도의 풀이가 필요하다는 것, 남은 시간을 보고 F1을 긁기로 결정했다. 각 숫자의 인덱스를 모두 저장해 두고 없는 숫자, 2개 이상인 숫자를 파악하여 오른쪽으로 빼는 개수별로 시행해야 하는 횟수의 최솟값을 구하여 답을 구했다.