A. Row $\!$
0과 1로 이루어진 string이 주어지는데, 1이 인접해 있거나 1을 인접하게 하지 않고 0 자리에 1을 넣을 수 있으면 No를, 그 외에는 Yes를 출력하는 문제이다.
문제에서 얘기한 대로 구현하면 된다.
문제에서 Yes인 경우를 "maximal"하다고 표현했는데 아마 이 표현때문에 많은 사람이 헷갈렸을 것이다.(물론 나도) 1이 최대로 포함되어있지 않은 경우도 문제조건만 맞으면 Yes를 출력하면 된다. 예를들어서 01010 같은 경우는 10101이여야 1이 최대가 되지만 01010에서 1이 인접하지않고, 또한 1을 넣을 수 없으므로 Yes다.
distinct한 배열과 0과 1로 이루어진 string이 주어진다. string을 순서대로 돌며 문자가 0인 경우 주어진 배열 중에서 가장 작은 값을 배열에서 지우고 후보에 올린다. 문자가 1인 경우 지금까지 얻은 후보중에서 가장 큰 값을 후보에서 지우고 선택한다. 이 때 후보에 오르는 배열값의 index와 선택하는 배열값의 index를 순서대로 출력하는 문제다.
주어진 배열을 오름차순으로 정렬한 뒤,(vector를 쓸거면 내림차순으로 정렬하고 pop_back을 쓰는게 더 깔-끔) 0이 들어오면 선택하지않은 가장 작은값의 index를 출력하고 그 값을 priority_queue에 넣는다. 1이 들어오면 pq의 top에서 빼고, 그 값의 index를 출력하면 되는 문제다.
index를 얻기위해 pair의 first값을 value로, second값을 index로 주고 정렬하거나 pq에 넣어서 풀었는데, 각 값들이 distinct하므로 map을 이용하면 깔끔하게 짤 수 있다.
tree가 주어진다. 그 tree에서 어떤 edge를 잘랐을 때 두 component(tree)의 vertex의 개수가 모두 짝수일 때 그 edge를 자를 수 있다. 최대로 자를 수 있는 edge개수를 구하는 문제다. 자를 수 없는 경우 -1을 출력한다.
Codeforces-C. Kuro and Walking Route문제 하휘호환 문제다. 먼저, vertex의 개수가 홀수이면 어느 경우에도 -1이다. 짝수인 경우에는 각 vertex의 subtree의 개수를 구하여 subtree개수 + 1값이 짝수이면 그 vertex를 포함하는 subtree는 원래의 tree에서 잘릴 수 있다. 잘라내도 짝수개를 잘라냈기 때문에 짝, 홀이 변하지 않기 때문에 짝수의 개수만 찾아내면 된다. 짝수의 개수만큼 tree가 생기므로 짝수의 개수 - 1개가 자를 수 있는 최대 edge의 개수다.
보자말자 코딩하고 제출했는데 틀렸다. 홀수를 미리 처리해준다고 생각은 했는데 생각 검증한다고 키보드에 손 놓았다가 처리해준다는걸 깜박했다. dp로도 가능하다는데 dp로 짜면 훨씬 더 어려워질것같다.
배열이 주어진다. 배열의 값 $a_i$는 $i$번째 날에 상어가 움직인 거리를 나타낸다. 상어가 $k$미만만큼 움직이면 상어는 아직 그 구역에 있다는 말이고, $k$이상만큼 움직이면 상어는 다른 구역으로 이동한다는 말이다. 상어는 방문한 모든 구역을 똑같은 날동안 머물러야한다. 이때 상어가 방문할 수 구역을 최대화시키는 $k$를 찾고, 그 $k$를 최소화 시켜서 출력하는 문제다.
예를들어, 25 1 2 3 14 36라는 입력이 들어오면 $k$는 2다. 3이되어도, 14가 되어도, 심지어 36, 37이 되어도 방문한 구역은 항상 1개이지만, 가장 작은 $k$는 2이다. 1이면 방문하는 구역이 아예 없이 계속 이동만 하므로 방문 구역이 최대가 아니다.
간단하다. 먼저 입력으로 들어온 배열을 오름차순으로 정렬한다. 그 다음 작은 값부터 for-loop를 돌면서 그 값의 index를 구역을 이동하지않고 구역에 머무른값으로 보게되면, 모든 각 구역의 크기가 같고, 구역의 개수가 최대일때 k를 갱신해주게되면 원하는 정답을 얻을 수 있다.
문제를 보고 dp나 greedy는 아닌것같고 graph나 tree쪽일 것같다는 느낌이 강하게 와서 그 쪽으로 접근해보다가 배열 하나만 들어오길래 왠지 정렬해보고 싶어서 정렬하고, 배열에 색칠해나가면서 색칠된 component를 센다는 느낌으로 생각해서 접근하니 disjoiint-set이 생각나서 바로 뚝딱뚝딱해서 짜잔! 했더니 WA. 틀린 이유는 제일 큰 component가 갱신되었을 때 남은 제일 큰 component와 size가 다른 녀석들을 총 component개수 - 1 개로 설정해야하는데 0개로 설정하는 바람에 WA였다. A번에서 너무 시간을 많이 끌어서 시간이 부족해서 성급했던 거같다.
그리고 배열에 있는 값으로 $k$를 갱신하고 난 뒤, 출력은 $k + 1$로 해야한다. 배열의 값으로 $k$를 결정했는데 $k$와 같은 값은 구간을 이동해야하기때문에 $k + 1$로 해야 그 값을 구간에 머무르는 값으로 설정할 수 있다. 이걸 생각 못 했던게 처음엔 배열에 있는 수들 중 $k$인 수 다음 수($k$보다 큰 가장 작은 수)로 출력했는데 주어진 예제에서는 $k$값과 $k + 1$값이 모두 배열에 주어지기때문에 값이 정답과 같았기 때문이다.
A번에서 시간 좀 아꼈으면 D번도 풀 수 있었는데 너무 아쉬웠다.
