CodeForces Round 959 - Div 1.5

https://codeforces.com/contest/1994

 

 

Performance Rating : 2300

 

A

1부터 $nm$까지의 수를 모두 다르게 만들어야 하므로 $n=1$, $m=1$인 경우 안된다는 예외 처리를 해주고 $a_{i,j}=a_{i,j}%(nm)+1$을 해주면 모두 다른 숫자로 바꿀 수 있다.

 

B

문자열에서 1이 나오기 시작하는 위치부터는 모든 자리를 원하는대로 바꿀 수 있다는 생각을 했다. 그러므로 $t$에서 1이 먼저 나오기 시작한 경우에는 "NO"를 출력해주면 된다. $s$에서 1이 먼저 나오기 시작했을 때를 생각해보아야 하는데, 1이 나오기 전까지 0을 1로는 못바꾸지만 1은 자유롭게 0으로 바꿀 수 있으므로 나머지의 경우는 모두 "YES"일 것이라고 생각했다.

 

C

풀이가 바로 떠오르지 않아 당황했다. 결국 dp를 활용해야겠다는 생각이 들어 dp 점화식을 떠올려 보았다. $dp[i]$를 $j\leq i$인 $j$에 대해 $[l,r]$구간을 잡았을 때 0이 되는 $j$의 개수라고 정의하면 dp로 해결이 가능할 것 같았다. $a_i+\cdots +a_j>x$이고, $a_{i+1}+\cdots +a_j\leq x$이면 $dp[i]=dp[j]+1$이 된다는 식을 세웠는데 구현이 발목을 잡았다. 여러번의 시행착오 끝에 맞는 구현을 했다.

 

D

1은 어떤 두 수를 묶어도 되기 때문에 1부터 사용하는 것은 바보짓이라는 생각을 하면서 문제를 바라봤다. 결국 두 수를 $(n-1)$로 나눈 나머지가 같은 것이 가장 만족하기 힘든 조건이기 때문에 $(n-1)$부터 처리를 해줄 생각을 해보니 숫자의 개수가 딱 $n$개라서 비둘기 집의 원리로 $(n-1)$로 나눈 나머지가 같은 것이 존재하고 이 2개를 묶어주면 되겠다는 생각으로 풀었다. 마찬가지로 구현에서 발목을 잡혀 예제에서 틀렸는데 나머지가 같은 2개를 찾고 나서 break문을 작성해주지 않은 것이 문제였다.

 

E

트리에는 무조건 리프 노드가 있으므로 정점의 개수 이하의 모든 숫자를 만들 수 있다는 것을 떠올렸다. 그러므로 트리가 어떻게 생겼는지는 중요하지 않을 것이라 생각했다. bitwise or의 특성상 최상위 비트가 이미 1이라면 그 미만의 모든 비트를 1로 만든 숫자를 bitwise or 해주는 것이 이득이라는 것을 생각하여 풀이를 제출했으나 WA를 받았다. 반례를 생각하다가 10100 1100의 경우 최상위 비트가 0이라고 해서 그대로 bitwise or을 해주는 것 보다 1011을 bitwise or 해주는 것이 더 커진다는 것을 알게 되었고 최상위 비트부터 0인 경우에는 아래 비트를 봐주고 1인 경우에는 하위 비트를 모두 1로 바꾼 것을 bitwise or 해주는 것으로 코드를 고쳤다.

 

F

결국 NPC가 서있는 도로에 NPC가 없는 도로 몇개를 추가하여 오일러 회로를 만들 수 있는지 즉 모든 정점의 차수를 짝수로 만들 수 있는지를 묻는 문제였다. 하지만 모든 정점의 차수를 짝수로 만드는 방법을 떠올리지 못해 풀지 못했다.