2021-08-21 Problem Solving

이번에도 문제를 비교적 꾸준하게 풀었던 것 같다. 특히, 이번 주 부터는 ho94949님, dennisstar님과 함께 하루에 랜덤 문제 5개를 뽑아서 하나 이상 푸는 챌린지를 하고 있어서 (나 말고 나머지 두 분은 웬만해서 거의 다 풀긴 하는듯) 더 자극이 되었던 것 같다.

20986. Group Photo

1번부터 $i$번까지만 생각해주는 방식으로 DP를 할 수 있다. 이 DP를 효율적으로 하는 방법에 대해서 생각해보면 되는데, $i$ 앞에 $j$가 오는지의 여부를 $N^2$개의 쌍에 대해 전부 이차원 배열에 구해둔 뒤, $x$축과 $y$축 두 방향 모두에 대해서 prefix sum 전처리를 해두고 활용할 수 있다.

15759. Talent Show

1000을 곱해주는 귀찮은 부분은 따로 빼두고 생각하자. 어쨌든, 출력 값이 정수이기 때문에, 고정된 $x$에 대해 "talent sum과 weight sum의 비율을 $x$ 이상이게 할 수 있는가?" 라는 결정 문제를 해결하는 방향으로 접근할 수 있다.

 

그러면, 결정 문제가 참일 필요-충분조건을 고려해보자. 먼저, 다음과 같은 식으로 쓸 수 있다.

$$ {\sum t_i \over \sum w_i} \ge x $$

이는, 다음 식과도 같다.

$$ \sum (t_i - x w_i) \ge 0$$

결국, 무게가 $w_i$이고, 가치가 $t_i - x w_i$인 물건을 담는 냅색 문제를 해결하면, 결정 문제도 해결할 수 있다.

6216. Protecting the Flowers

Swapping argument를 생각해보면, $D_i / T_i$ 순으로 정렬하면 됨을 쉽게 알 수 있는 문제다.

22348. 헬기 착륙장

다이나믹 프로그래밍을 이용해 접근해보자. $D[r][x]$를 $r$개의 동심원을 정확히 $x$통의 빨간색 페인트를 사용하며 칠하는 경우의 수로 정의할 수 있다. 그러면, $D[r][x] = D[r-1][x] + D[r-1][x-r]$의 점화식이 성립할 것이다. 이 다이나믹 프로그래밍 테이블을 전처리 해두었다고 가정하자.

 

이제, 질의로 빨간색 $a$통, 파란색 $b$통을 사용하는 상황이 주어졌다고 가정하자. 그러면, 각각의 $r$에 대해 따져봐야 하는 경우는 $r(r+1)/2 - b \le x \le a$인 경우의 $D[r][x]$ 값들이 된다. 결국, 가능한 $x$의 범위가 연속적으로 나타내기 때문에, 다이나믹 프로그래밍 테이블을 각 행 마다 prefix sum 전처리를 해두게 되면, 하나의 $r$ 값에 대해 $O(1)$ 시간에 답을 구할 수 있다.

 

주어진 $a, b$에 대해 가능한 $r$ 값은 총 $O(\sqrt{a+b})$개 있으므로, 앞서 서술한 전처리를 잘 해두면, 질의당 $O(\sqrt{a+b})$ 시간에 처리할 수 있다.

15471. A Simple Function

엄밀히 증명은 해보지 않았는데, 대충 값 찍어보고 규칙을 찾았고, 잘 생각해보면 루카스 정리 처럼 되지 않을 이유가 없어서 적당히 믿음을 가지고 짰다...

3737. Cycle of Lanes

문제의 조건 때문에, 각 BCC를 보면서 절선이 아닌 간선의 수를 세어 주면 되는 문제로 바꿀 수 있다. 결국, BCC를 구하는 것이 이 문제의 풀이에 있어 핵심이다. BCC 같은 경우에는 DFS 트리를 응용해서 구해줄 수 있는데 (나는 처음 짜봤다) DFS 트리의 역방향 간선을 볼 때 잘 처리해주면 된다.

4196. 도미노

SCC를 정점으로 해서 그래프를 압축하자. SCC DAG에서 in-degree가 0인 SCC의 개수가 문제의 답이 된다.

 

나머지 풀었던 문제들은 UCPC 문제들이거나, 풀이를 쓸 정도로 흥미롭지는 않았다.