총평
문제들은 다음 링크에서 확인할 수 있다.
http://codeforces.com/contest/1481
A~E가 전부 무난했다. F를 푸는데는 실패해서 아쉽다. 시스텟 전엔 40위로(div1+div2) 순위 준수한 성적을 기록했다. 저번 에듀를 안 쳤으면 rated 중엔 7위, top10 이었을 것 같다. 다음은 각 문제의 풀이다.
A
좌표가 주어지고, 문자열 S가 주어진다. 각 문자는 L,R,U,D로 구성되어 있고, 각각 왼쪽, 오른쪽, 위쪽, 아래쪽으로 1씩 움직이라는 뜻이다. 이때, 문자 중에 몇 개를 제거해서 (0,0)에서 원하는 좌표로 이동할 수 있는지 묻는 문제이다. 주어진 문자열을 통해 도달 가능한 x좌표, y좌표의 최댓값, 최솟값을 알 수 있으므로, 주어진 좌표가 그 범위안에 들어가는지 판별해주면 된다. 개인적으로 A치곤 살짝 어려웠다.
B
정수들이 있는 배열이 주어지는데, 다음 원소보다 지금 원소가 크거나 같으면 계속 진행, 그렇지 않으면 현재 원소를 1 증가 시키고, 끝까지 도달하면 전체 작업을 끝낸다. 이때, k번째 작업이 어디에서 끝나는 가를 묻는다. 제한을 생각하지 않고 풀면 어렵게 접근할 수 있다. 주어지는 배열의 길이도 100이하, 최댓값도 100 이하이므로, 그냥 시뮬레이션을 돌리면서 배열이 내림차순이 될 때까지 진행시키면 된다.
C
원래 수들이 있는 배열, 목표로 하는 상태의 배열이 주어진다. 그리고, 순서대로 정확히 하나의 원소를 특정 값으로 바꿀 수 있다. 이때, 원래 배열의 값을 적절히 바꾸어 목표로 하는 상태로 바꿀 수 있는 가를 묻는 문제이다. 이 문제를 풀 때 주의해야 하는 것은 한번 값을 바꾼 원소의 값을 또 바꾸는 것이 가능하다는 것이다. 그렇기 때문에, 순서대로 보는 것이 아니라 일단 전부 받은 후 역으로 보는 것이 문제를 더 편하게 풀 수 있다. 처음과 값이 달라져야 하는 부분, 같아야 하는 부분을 우선 구분한 뒤, 뒤에서 부터 보면서 처음과 값이 달라져야 하는 부분에 우선적으로 매칭을 시킨다. 이때, 매칭 하는 값이 하나도 없다면, 역으로 보고 있으므로 이미 매칭된 아무 값에 매칭을 시킨다. 이렇게 했을 때 매칭 하는 곳을 못 찾거나, 값이 바뀌어야 하는데도 그렇지 못 한 값이 남아있으면 NO, 아니면 YES이다.
D
아이디어 문제, 우선 어떤 두 정점 x,y가 있어 x->y, y->x에 대해서 쓰여 있는 문자가 같다면 x, y, x, y, …. 와 같으로 순회하면 같은 문자로 구성된 임의의 길이의 문자열을 항상 만들 수 있다. 이것은 자명하게 팰린드롬이다. 그렇지 않다면, 모든 정점 x,y 에 대해서 x->y, y->x에 쓰여 있는 문자가 다르다는 뜻이므로, x, y, x, y, …. 와 같이 순회할 경우, abababab… 또는 babababa…같은 문자열이 된다, 이때, 길이가 홀수이면, 이 문자열은 팰린드롬이되므로, 그대로 출력한다. 만약 짝수라면, n = 2일 경우 모두 불가능하다. 그 외에는 어떤, 정점 x,y,z가 존재하여, x->y에 쓰여진 글자는 a,x->z에 쓰여진 글자는 b인 x,y,z가 항상 존재한다. (증명은 간단하다.) 따라서 순서를 잘 조정해서 출력하면 된다.
E
E치고는 간단하다고 생각한 문제, 관찰은 책을 선택할 때 많아봤자 한번 선택하면 된다는 것 && 그리고 선택되지 않은 책들의 순서가 변하지 않고, 나머지 책들을 제거하면 조건을 만족시켜야 한다는 것이다. 따라서 dp를 쓰면 간단하게 풀린다. 정리된 책들의 배열을 생각했을 때 어떤 수 i가 존재하여 위치가 i이하인 책들은 뽑히지 않았고, 그 뒤의 책들은 뽑힌 책들이 되게 할 수 있으므로, 이 점에 착안하여 dp를 하면 된다.