오늘의 PS (13) - 220619

ARC랑 코포 Div.2를 쳤다.

 

ARC 142

글로는 먼저 적었지만, 앞선 코포로 인해 멘탈이 별로였기에 제출을 막 했더니 페널티가 망했다.

 

A. Reverse and Minimize (0:08, +4) *552

문제 지문을 잘 읽고 여러 예외 상황들을 고려한 뒤 코딩을 시작하면 어렵지 않게 구현할 수 있다. 나는 예외처리같은거 없이 막 냈다가 4번 틀렸다.

 

B. Unbalanced Squares (0:17, +1) *692

아이디어 원툴 Constructive 문제이다. 많은 방법이 있겠지만, 내 방법은 x좌표와 y좌표가 모두 짝수인 곳부터 차례대로 숫자를 채운 뒤, 남은 숫자를 모두 채우는 것이다. 이러면 전자의 경우는 무조건 인접 8방향이 자신보다 크며, 후자의 경우는 잘 세어보면 항상 규칙을 만족한다는 것을 알 수 있다.

 

C. Tree Queries (0:58, +7) *1347

앳코더에서 보기 힘든 인터랙티브 문제이다. 우선, 1과 다른 모든 노드에 대해 쿼리를 날리자. 이러면 세 가지 정도로 케이스를 나눌 수 있다.

1. 1과 거리가 1인 노드가 0개인 경우

 이 경우는 무조건 1과 2의 거리가 1이다.

2. 1과 거리가 1인 노드가 2개 이상인 경우

 이러면 해당 노드들과 2의 거리를 조사하는 것으로 정답을 알아낼 수 있다.

3. 1과 거리가 1인 노드가 1개인 경우

 이 경우 1과 2의 거리가 1인 경우와 그렇지 않은 경우로 나뉘는데, 이는 각자만의 기준을 잘 나누어 판단하면 된다. 내 방법은 별로 깔끔하지 않은 것 같아 소개하지 않는다.

 

 

Codeforces Round #802 (Div. 2)

6시에 눈을 떴을 때 그냥 다시 잤어야 했는데..

A. Optimal Path (0:01, +)

간단한 식 정리이다.

 

B. Palindromic Numbers (0:17, +)

1000..001에서 빼주면 항상 답이 될 줄 알았으나, 예제부터 나오지 않길래 앞자리가 9라면 111..111에서 빼는 것으로 따로 분류해주었다. 잠에서 덜 깬 상태라 구현이 상당히 늦었다.

 

C. Helping the Nature (0:52, +1)

간단해 보이지만 꽤나 어려운 그리디 문제이다. 앞에서부터 보면서 내가 다음 원소보다 크다면 prefix 쿼리, 그 반대라면 suffix 쿼리를 써준 후 적절한 쿼리로 모두 0으로 만드는 방법이 최적이다.

 

D. River Locks (1:49, +5)

각 경우에 대해서 앞 \(i\)개의 파이프를 키는 것이 최적임은 쉽게 관찰할 수 있다. 이를 잘 관리하면서 모든 열린 파이프의 개수에 대해 물이 모두 차는 시간을 구해준 후, 각 쿼리마다 이분 탐색으로 답을 구하면 된다. 나는 식 정리를 진짜 못해서 제출도 막 하고 시간도 오래 걸렸다.

 

역시나 2090점에서 떨어졌다ㅜㅜ