[Codeforces] Round #504

http://codeforces.com/contest/1023

 

굉장히 잘 친줄 알았는데 E번이 시스텟에서 나가 아쉬웠습니다.

 

A - Single Wildcard Pattern Matching (Code)

 

*이 존재하지 않는다면 두 string이 동일한지 확인하면 되고, *이 존재한다면 우선 s의 글자수가 t의 글자수 - 1 이상인지를 먼저 확인합니다. 이후 *이 등장하기 전의 s의 앞 부분이 t의 앞 부분과 일치하는지 확인하고 *이 등장하기 전의 s의 뒷 부분이 t의 뒷 부분과 일치하는지 확인합니다. hack이 엄청 터져나왔습니다.

 

3 7

a*a

aaaaaaa 로 hack에 성공했습니다.

 

B - Pair of Toys (Code)

 

6 8를 예로 들면, 8을 만들 수 있는 방법은 1+7, 2+6, 3+5가 있는데 두 수 중에 큰 수가 N 이하이기만 하면 작은 수가 N 이하임은 자명합니다. 그러므로 $min(N, K-1) - K / 2$를 계산해주기만 하면 됩니다. 두 수가 같아서는 안된다는 조건을 잘못 봐 한 번 틀렸습니다.

 

C - Branket Subsquence (Code)

 

저는 stack에다가 ( 의 index를 넣어두고 )가 들어올 때 마다 해당 )에 대응되는 (와 )의 index에 unused임을 명시해두어 (N-K)/2 개의 쌍을 제거하는 방식으로 해결했고, 이외에도 그냥 앞에서부터 (, )를 (N-K)/2개 제거하는데 이 때 지워지는 )는 (보다 뒤에 위치하게끔 하는 방식으로도 간단하게 해결이 가능합니다.

 

D - Array Restoration (Code)

 

관찰을 좀 하다보면 1을 제외한 나머지의 경우 그 값이 쓰여야하는 구간이 고정됨을 알 수 있습니다. 그 구간은 해당 값이 나오는 최초의 지점에서부터 해당 값이 나오는 마지막 지점입니다. 그리고 1은 그냥 전체에 다 써버리면 됩니다.

 

예를 들어 1 2 3 3 2 2 4 0 4 1 1 일 경우

 

1은 1에서 11까지 쓰이고, 2는 2부터 6까지 쓰이고, 3은 3부터 4까지 쓰이고, 4는 7부터 9까지 쓰이는 것입니다. 이제 이렇게 구간을 복원하고 나면 실제로 이 구간대로 Array를 복원한 뒤 기존의 Array와 일치하는지 확인하면 됩니다. 복원할 때 segment tree를 활용해도 되고 저는 priority queue를 활용했습니다. 단 이 때 주의해야 하는 것은 복원된 Array에 Q는 반드시 등장해야하므로 만약 기존의 Array에 Q도 없고 0도 없으면 불가능합니다. Q가 없는데 0이 있으면 그 0 중 아무거나 하나를 Q로 강제로 두어야 합니다.

 

E - Down or Right (Code)

 

manhattan 거리 제약조건을 무시하고 문제를 한 번 풀어봅시다. 그렇다면 그냥 (1,1)부터 시작해서 오른쪽 혹은 아랫쪽을 잘 골라가기만 하면 되는데, 현재 위치를 (x,y)라고 한다면 (x+1, y, N, N)을 질의해 YES라면 아랫쪽으로, NO라면 오른쪽으로 가기만 하면 됩니다.

 

이제 manhattan 거리 제약조건이 있는 경우를 생각해봅시다. 제약조건이 있더라도 일단 왼쪽 아래와 오른쪽 위를 연결하는 대각선까지는 (N,N)까지의 거리가 N-1 이상이므로 도달할 수 있습니다. 이제 이 곳에서부터 (N,N)까지 가는게 문제인데, 이제는 반대로 (N,N)에서 시작해 (1,1)까지 왼쪽 혹은 위쪽을 골라서 찾아간다고 생각해보면 마찬가지로 manhattan 거리 제약조건을 위배하지 않으면서 대각선까지 도달할 수 있습니다.

 

이제 걱정되는 것은 (1,1)에서 출발해 대각선에 도달한 지점과 (N,N)에서 출발해 대각선에 도달한 지점이 일치하지 않으면 어떡하나일텐데, (1,1)에서는 오른쪽으로 먼저 가보고, (N,N)에서는 위쪽으로 먼저 가본다면 문제가 없습니다.

 

귀류법으로 생각해보면 (1,1)에서 출발해 대각선에 도달한 지점이 (N,N)에서 출발해 대각선에 도달한 지점과 일치하지 않고 더 왼쪽 아래에 위치해도 모순, 오른쪽 위에 존재해도 모순이 발생함을 알 수 있습니다.

 

A,B,C는 굉장히 빠르게 풀어냈는데 D, E에서 다소 시간이 지체됐고 아예 E는 system test를 통과하지 못한게 많이 아쉽네요. 2200 언저리를 가나 싶었는데 ㅠ_ㅠ