[Codeforces] Educational Codeforces Round 37

A B C는 그럭저럭 풀만했고 E F는 조금만 더 잘했으면 풀 수 있었을 것 같았지만 접근을 조금 잘못해 풀어내지 못했습니다. G랑 D는 제 능력 밖의 문제였던 것 같습니다. 독특하게 D의 정답자가 가장 적었습니다. 저는 A, B, C를 각각 6분, 23분, 39분에 Accepted, E는 WA를 받아 총 3문제를 해결했습니다. E를 못 푼 것과 B를 풀 때 다소 많은 시간이 걸린 것 이 2가지가 많이 아쉬웠습니다.

 

A - Water The Garden

 

입력으로 들어온 water tap들을 a[0], a[1], ... ,a[k-1]라고 한다면 max(a[0], (a[1]-a[0])/2+1, (a[2]-a[1])/2+1, ... , (a[k-1]-a[k-2])/2+1, n-arr[k-1]+1)이 답입니다. 물이 어떻게 전파되는지를 생각해본다면 쉽게 이해가 갈 것입니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Educational%20Round%2037/A.cpp

 

B - Tea Queue

 

조건 상으로 학생들이 순차적으로 온다는 것이 보장되기 때문에 그냥 순차적으로 학생들을 한 명씩 살피며 처리를 해주면 됩니다. 맨 처음에는 직접 큐로 짜다가 뭔가 꼬여서 다 들어내고 새로 짜느라 시간이 조금 오래 걸렸습니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Educational%20Round%2037/B.cpp

 

C - Swap Adjacent Elements

 

맨 처음에는 아이디어가 없어서 조금 당황했는데 다행히 빠르게 아이디어를 잡아낼 수 있었습니다.

 

배열에서 (i, i+1)번쨰 원소의 위치를 바꿀 수 있고, (i+1, i+2)번째 원소의 위치를 바꿀 수 있고, ... (j-1, j)번째 원소의 위치를 바꿀 수 있으면 i번째부터 j번째까지의 원소는 임의로 재배열을 할 수 있습니다.

 

그렇기에 문제 상에서 1이 연속한 것을 기준으로 구간을 나눠 그 구간 내에서는 자유롭게 원소의 재배치가 가능하므로 속해있어야하는 모든 수가 들어가있는지 판단합니다.

 

예를들어

 

6

1 2 5 3 4 6

01010

 

인 경우, 구간을 1 / 2 5 / 3 / 4 6 / 으로 나눌 수 있습니다. 이 때 두 번째 구간에 2 3이 들어있어야 하는데 2 5가 들어있으므로 답이 NO임을 알 수 있습니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Educational%20Round%2037/C.cpp

 

레이팅은 아주 매우 소량 상승했습니다.