Educational Codeforces Round 102 (Rated for Div. 2)

 

방학 기간에 동아리 부원들과 1일 1버츄얼을 돌리기로 했다.

A. Replacing Elements (0:02, +)

정렬을 한 후, \(d\)보다 큰 수는 \(a_1 + a_2\)로 바꿔주어야 한다. 

 

B. String LCM (0:06, +)

길이를 \(|s||t|\)까지만 확인해보면 된다. 그냥 짜주자.

 

C. No More Inversions (0:30, +1)

그냥 밑바닥에서 규칙을 찾아야 하는 코포식 문제다. 뭔가 해보다 보면 대칭인 부분을 잘 뒤집어주면 된다는 사실을 알 수 있다. 자세한 증명은 에디토리얼에 있다.

 

D. Program (0:42, +)

더하는 수가 +-1로 연속적이므로 누적합의 최댓값과 최솟값을 구하면 된다. 앞에서부터의 최대, 최솟값과 뒤에서부터의 최대, 최솟값을 저장하면 해결할 수 있다. 나는 귀찮아서 세그를 박았다.

 

E. Minimum Path (1:25, +)

max랑 min에 너무 집중해 고정한다던가 하는 시도를 하면 말릴 수 있다. max를 빼는 것은 간선 중 하나를 골라 비용 0으로 만드는 것으로 생각할 수 있고, min을 더하는 것은 간선 중 하나를 골라 비용을 2배로 만드는 것으로 생각할 수 있다. 즉, 후자를 구하면 그에 대한 답이 원본 문제가 됨이 자명하다. 이 문제를 해결하는 것은 두 연산에 대한 상태를 0과 1로 표현하면 정점 \(4N\)개로 그래프를 표현할 수 있다. 이 그래프에서 다익스트라를 쓰면 된다.

 

F랑 G도 풀어볼 가치가 있는 것 같다. 업솔빙 예정