ABC 396

https://atcoder.jp/contests/abc396

 

 

Performance Rating : 1616

 

A

$v[i-1]=v[i]=v[i+1]$인 $i$가 존재하는지 찾는 문제였다.

 

B

평범한 스택 문제였다.

 

C

어떤 색깔의 공을 고르던 있는 공 중 가장 큰 것을 뽑는 것이 이득이고 흰 공의 경우에는 검은 공 개수 이하로 고를 때 최댓값을 찾아주어야 한다. 그러므로 정렬과 누적합, 누적 최댓값을 활용하여 답을 구했다.

 

D

$N\leq 10$이라는 점에 주목했다. $O(N!)$이 충분히 돌아가는 작은 수이기 때문에 모든 경로를 다 살펴볼 생각을 했다. $1$부터 $N$까지의 수가 모두 있는 $N!$개의 순열을 생각하자. 각 순열에서 $1$과 $N$사이에 있는 숫자들을 순서대로 방문한다고 생각하면 모든 경로를 다 볼 수 있다. $N!$개의 수열에 대해 경로의 값을 모두 구해 최솟값을 구해주면 답을 구할 수 있다. 답이 $10^{18}$보다 큰 경우가 있는데 $LINF$의 값을 $10^{18}$으로 두어 WA를 한번 받았다.

 

E

그래프 모델링을 하면 풀릴 것 같았다. $X_i$와 $Y_i$를 가중치가 $Z_i$인 간선으로 연결한다고 생각했다. 사이클 중 간선의 가중치를 모두 Bitwise xor 했을 때 0이 나오지 않는다면 -1을 출력하면 된다. 그런 사이클이 없다면 한 정점의 값 0으로 두었을 때 그 정점과 연결된 다른 모든 정점들의 값을 구해놓고 비트별로 개수를 세어 합을 최소로 만들어줄 생각을 했다. 디버깅 과정에서 for문의 범위를 실수하여 한 번의 WA를 받고 for문의 범위를 고쳤음에도 WA가 나왔다. 당연히 맞은 줄 알고 F에 넘어갔다가 F를 풀고 E를 틀린 것을 확인한 뒤 다시 돌아왔다. 논리상 틀릴 것이 없다고 생각하여 한참을 고민하다가 비교연산이 비트연산보다 우선순위가 큰데 비트연산에 괄호를 씌우지 않아 틀렸다는 것을 30분 만에 발견했다. 비트연산자에는 괄호를 씌우는 것을 습관화해야겠다.

 

F

$A$에서 inversion number을 구해주고 $A_i=A_i+1\;\mathrm{mod}\;M$으로 바꾸는 과정을 $M-1$번 해주는 것으로 생각했을 때 inversion number에 어떤 변화가 생기는지 살펴보니 다른 숫자들의 크기 관계는 변경되지 않고 가장 큰 수가 가장 작은 수로 바뀌기만 한다는 것을 관찰했다. 따라서 각 숫자의 인덱스 번호만 저장해두면 $A_i=A_i+1\;\mathrm{mod}\;M$으로 바꾸었을 때 inversion number을 구해줄 수 있으므로 이를 통해 구했다.

 

G

E에서 너무 많은 시간을 낭비해 문제를 고민할 충분한 시간이 남지 않았다.