CodeForces Educational Round 174

 

https://codeforces.com/contest/2069

Performance Rating : 2700
 
A
처음에 조금 당황했는데 잠깐 생각해 보니 B에 1 0 1이 있는지 판단하는 문제였다.

B
체스판칠을 하면 하나의 색깔을 무조건 2번에는 원하는 색으로 바꿀 수 있다. 그래서 인접한 같은 색이 있으면 2, 없으면 1이 된다. 이를 구현해 맞았다.

C
문제를 보고 DP가 아닐 수 없다고 생각했다. 길이가 3 이상인데 2인 것도 포함하는 것을 짰다가 길이 3 이상이라는 것을 알고 수정했다.

D
우선 양 끝에서 $s[i]=s[n-i-1]$이면 볼 필요가 없다는 것을 생각했다. 이후 바꾸지 않을 substring을 고를 때 그 substring에서 남은 string의 알파벳의 개수 중 반을 넘게 가져가면 안 된다는 것을 알게 되었고 이를 바탕으로 짰는데 빼먹은 케이스가 있었다. 앞과 뒤를 구성하는 알파벳 종류별 개수가 같으면 가운데부터 $s[i]=s[n-i-1]$인 부분도 빼줘도 된다는 것이다. 이를 깨닫고 코드를 고쳐 맞았다.

E
일단 3개 이상 연속하는 것은 무조건 A or B로 해결해야 하므로 2개 이하로 연속하도록 문자열을 바꿔줬다.  처음에는 아무 생각 없이 그리디로 짰다가 WA를 한번 받았다. 이후 같은 2개가 연속하는 것 앞뒤로 문자열을 자르면 그리디가 가능해진다는 것을 알게 되었다. 이를 저장해 준 뒤 정렬과 그리디를 통해 해결했다.

F
문제를 보자마자 오프라인 동적연결성 판정을 쓸 수밖에 없겠다는 생각을 했다. 하나는 A와 B 간선을 모두 저장하고 하나에는 A 간선만 저장하여 그룹 개수의 차이를 출력하면 된다는 것을 30분 남았을 때 알게 되었고 구현을 시작했다. 하지만 시간 안에 구현을 못했고 업솔빙을 했다.