[Codeforces] Educational Codeforces Round 36

http://codeforces.com/contest/915

 

코드포스 라운드 시간대가 툭하면 밤 11시 30분, 새벽 0시 30분 막 이래서 참가할 엄두를 못내다가 밤 10시 5분부터 진행되는 라운드가 있길래 참가했습니다.

 

총 7문제였고 A B C는 Accepted, D는 알고리즘은 맞았으나 구현상의 실패로 Runtime Error, E는 문제는 읽어봤으나 알고리즘 접근을 잘못했고 F G는 한번 쓱 훑어보고 바로 넘겼습니다.

 

A - Garden

 

div2의 A번이 원래 그렇듯 따로 설명이 필요없을 정도로 그냥 거저 주는 문제입니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Educational Round 36/A.cpp

 

B - Browser

 

왼쪽, 오른쪽 중에서 현재 위치에서 가장 가까운 곳으로 이동해 다 지우고, 이후 남은 쪽으로 이동해서 다 지우면 된다는 것만 찾아내고 나면 쉽습니다. 다만 left나 right가 끝에 닿아있을 때, left = right일 때 등의 예외처리를 꼼꼼하게 해줘야합니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Educational Round 36/B.cpp

 

C - Permute Digits

 

DP+Bitmask로 해결하는 풀이가 editorial에 올라와있는데 저는 아래와 같은 로직으로 해결했습니다.(Greedy에 가까운 것 같기도 하고..)

  

1. A에 등장하는 0~9의 갯수를 따로 저장해둡니다.

2. B의 자릿수가 A보다 많으면 A에 등장하는 갯수대로 9~0을 역순으로 출력합니다.

3. A의 자릿수와 B의 자릿수가 같음은 보장이 됐습니다. 이제 재배열된 A를 제일 앞자리부터 구해나갈 것 인데, 이를 위해서 현재 채울 자리에 B는 어떤 값이 들어가있는지를 봅니다. 그 값을 A의 그 자리에 넣을 수 있다면 그 값을 넣고 다음 자리를 봅니다.(어떻게 A의 그 자리에 넣을 수 있는지는 아래에 자세히 기술하겠습니다.) 만약 넣을 수가 없다면 A의 그 자리에는 B의 값보다 작으면서 가장 근접한 값을 넣고, 그 뒤는 9~0을 역순으로 대입하면 됩니다.

 

3번 과정의 예시를 들어보면

 

A : 12345

B : 41130

 

이라고 할 때, 10000의 자리를 봅니다. 최대한 A를 크게 하고 싶으므로 일단 재배열된 A의 10000의 자리에 4를 넣는다고 가정해봅시다. (4@@@@) 이 때 이 값은 41235 이상입니다. 그런데 41235는 B보다 크므로 재배열된 A의 10000의 자리에 4를 넣을 경우 다른 값들을 어떻게 두더라도 무조건 B보다 크게 됩니다. 그러므로 4를 넣는 것이 불가능하니 그 다음으로 3을 넣습니다. 3을 넣고나면 무조건 B보다 작음이 보장되므로 남은 수들을 최대한 크게 넣습니다. (35421)

 

또 다른 예시를 하나 더 들어보면

 

A : 51206

B : 26701

 

이라고 할 때 10000의 자리를 봅니다. 일단 재배열된 A의 10000의 자리에 2를 넣는다고 가정해봅시다.(2@@@@) 이 때 이 값은 20116 이상입니다. 20115는 B보다 작으므로 재배열된 A의 10000의 자리에 2를 넣어도 문제가 없음을 확인할 수 있습니다. 그러니 2를 넣고 1000의 자리를 살펴봅니다. 재배열된 A의 1000의 자리에 6을 넣는다고 가정해봅시다.  (26@@@) 이 때 이 값은 26015 이상입니다. 26015는 B보다 작으므로 마찬가지로 1000의 자리에 6을 넣어도 문제가 없음을 확인할 수 있습니다. 이제 100의 자리를 살펴보면, A에는 7이 없으므로 가지고있는 것 중에 7보다 작으면서 가장 큰 5을 넣고, 그 뒤로도 최대한 크게끔 대입합니다. (26510)

 

char와 int를 넘나들면서 구현이 아주 살짝 꼬였습니다만 의외로 빨리 잘 풀어냈습니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Educational Round 36/C.cpp

 

D - Almost Acyclic Graph

 

O(N+M)으로 주어진 Directed Graph에서 Cycle이 있는지 알아낼 수 있습니다. 주어진 Directed Graph에 Cycle이 없다면 바로 YES를 출력하면 되고, Cycle이 있다면 그 Cycle의 모든 edge에 대해 그 edge를 제거한 후에도 Cycle이 남아있는지 확인하면 됩니다. 시간복잡도는 O(N(N+M))입니다.

 

방법은 맞았는데 주어진 Directed Graph에서 Cycle이 있는지 판단하는 코드를 잘못 짜서 틀렸습니다.

 

E - Physical Education Lessons

 

라운드 중에는 1~N을 가지고 segment tree를 만들고 lazy propagation을 하면 되겠다 싶었는데, 그렇게 되면 공간복잡도가 대충 2N = 20억 정도니 말이 안된다는걸 깨닫고 바로 접었습니다. 대회가 끝나고 editorial을 읽어보니 1~N에서 segment tree를 만드는 대신 연속한 working day 구간을 원소로 가지는 tree를 만들어 각 쿼리에 대해 Insert/Delete를 수행하면 된다는 것을 알았습니다. 그렇게 되면 O(QlogQ)에 수행이 가능해집니다. 지금까지 한 번도 본 적이 없는 유형이었는데 좋은걸 배워가게 됐습니다.

 

D를 풀었으면 정말 좋았겠지만 그래도 다행히 A,B,C를 꽤 빨리 풀어내어 (4분/11분/34분) 126등에 안착했습니다.