오늘의 PS (12) - 220618

ABC랑 코포 Div.2를 쳤다.

 

ABC 256

A. 2^N (0:00, +) *7

이건 좀..

 

B. Batters (0:03, +1) *83

하라는 대로 구현해주면 된다. 이상하게 읽었다가 한번 틀렸다.

 

C. Filling 3x3 array (0:08, +) *541

좌상단 4개의 숫자만 정해주면 나머지는 모두 자동으로 정해진다. 따라서 \(O(30^4)\)에 문제를 해결할 수 있다.

 

D. Union of Interval (0:11, +) *546

백준에 널린 스위핑 기본 문제

 

E. Takahashi's Anguish (0:18, +) *1224

Functional Graph 형태이니 그림을 그려주자. 일자 형태는 잘 배치할 수 있는데, 사이클 형태는 하나를 끊어서 일자로 만들어주어야 한다. 이 때, 해당 사이클에 속한 정점 중 \(C_i\)의 최솟값들을 다 더해주면 된다.

 

F. Cumulative Cumulative Cumulative Sum (1:13, +3) *2067

식을 써보면 대충 \( A_x i(i+1) /2\) 의 합 형태가 나온다. 업데이트 쿼리로 인해 변경되는 값을 잘 써보면, \(x\) 보다 큰 인덱스는 이차함수 꼴의 변화량을 가진다는 것을 알 수 있다.

https://www.acmicpc.net/blog/view/88에 나오는 레이지 없이 레이지 풀기 테크닉을 이용해, 이차항의 계수, 일차항의 계수, 상수항을 관리하는 펜윅 트리 3개를 사용해주면 문제를 해결할 수 있다. 모듈러 연산도 많이 해야 하고, 전처리도 어느 정도 필요해 구현이 조금 까다로웠다.

 

Codeforces Round #801 (Div. 2)

A. Subrectangle Guess (0:06, +1)

해당 점으로부터 좌상단, 좌하단, 우상단, 우하단에 이르는 직사각형 넓이를 구한 후 최댓값을 출력하면 된다. \(n\)과 \(m\)을 헷갈려 한 번 틀렸다.

 

B. Circle Game (0:10, +)

더미의 개수가 홀수라면 선공이 첫 턴에 0으로 만들어버리면 되기 때문에 항상 선공이 승리한다. 더미의 개수가 짝수라면, 각 플레이어가 다루는 더미들이 변하지 않기 때문에 최대한 오래 게임을 유지하기 위해 1씩만 쓰는게 최선의 전략이다. 따라서, 모든 더미의 돌 개수중 가장 먼저 등장하는 최솟값을 구한 후, 인덱스의 홀짝성을 판별해주면 된다.

 

C. Zero Path (0:21, +)

재밌는 문제. 한 가지 관찰을 얼마나 빨리 하느냐에 따라 해결 시간이 정해진다.

해당 관찰은 다음과 같다: 경로에서 지날 수 있는 최소 1의 개수를 \(min\), 최대 1의 개수를 \(max\)라 할 때 \([min, max]\) 범위의 개수만큼 1을 지나는 경로가 항상 존재한다. 이는 ㄱ 모양으로 꺾인 길을 ㄴ 모양으로 바꿔줌으로써 1의 개수가 최대 1 변화하고, 이 과정을 반복함을 통해 모든 경로를 만들 수 있다는 사실을 통해 증명할 수 있다.

최소와 최대 개수는 쉬운 DP로 구해줄 수 있다.

 

D. Tree Queries (1:03, +1)

D1을 기준으로 생각하자. \(O(N^2)\) 이 가능하므로, 루트를 정한 후 시작한다는 발상을 할 수 있다. 또한, 풀이에 접근하기 위해서는 한 가지 관찰을 더 해야 한다: \(x\)개의 서브트리가 있다면, 이를 완벽히 구별하기 위해서는 최소 \(x-1\)개의 서브트리에서 해당 서브트리에 질문한 정점이 하나는 포함되어 있어야 한다.

이를 파악했다면, DFS를 하며 위와 같은 과정을 그리디하게 수행하며 (최대한 밑에서부터 질문하며) 답을 구해줄 수 있다.

D2는 이를 Tree DP 형태로 바꾸어주면 되는데, 식 정리를 1시간동안 못해서 못풀었다.

 

내일도 ARC와 Div. 2가 동시에 있다. 209x점으로 Div.2를 칠텐데, 이럴때 쳐서 잘 된 적이 없기에 너무 불안하다..