Atcoder Weekday Contest 070

Atcoder Weekday Contest 070 풀이

대회 링크는 아래와 같다

• link : https://atcoder.jp/contests/awc0070

1. A - Sorting Packages

• tag: implement
• link : https://atcoder.jp/contests/awc0070/tasks/awc0070_a

단순 구현, 설명은 생략한다.

2. B - Days of the Passing Line

• tag : implement, prefix_sum
• link : https://atcoder.jp/contests/awc0070/tasks/awc0070_b

누적합을 이용하면 $O(N)$에 가능하다.

3. C - Ways to Climb Stairs

• tag : dp -link : https://atcoder.jp/contests/awc0070/tasks/awc0070_c

1차원 dp를 쓰면 된다. $dp[i] : 현재 i번째 계단까지 오는 방법의 수$ 모듈러 연산에 주의(atcoder의 modint를 쓰거나 모듈러 연산을 "잘" 쓰면 된다.)

4. D - Switching the Lights

• tag : prefix_sum, imos
• link : https://atcoder.jp/contests/awc0070/tasks/awc0070_d

흔하디 흔한 2D imos

5. E - Delivery Person's Round

• tag : dijkstra, grid_dp, tsp
• link : https://atcoder.jp/contests/awc0070/tasks/awc0070_e

$K$개의 경유지를 거쳐야하니 $K$개만 놓고 생각하자. $K$의 범위가 15보다 작다는 것을 이용하면 다익스트라를 $K$번 돌려서 거리를 전처리하고, 그 다음 bitfield_dp를 이용해서 tsp를 돌리면 된다는 걸 알 수 있다. 구현도 쉽고 빠름.

총평

요새 하루에 Weekday 세트 하나씩 풀고 있긴한데 1시간 잡고 5문제 풀면 ㄱㅊ은 듯.