이번 주는 글을 미리미리 안써놔서 몰아쓰는 관계로 내용이 부실할 수 있다. 또한 날짜별 분류가 큰 의미가 없는 것 같아 앞으로는 구분하지 않겠다.
solved.ac 티어
20240212 기준 : Platinum I (μ = P1 - 0.16, σ = 0.38)
알고리즘 분류
solved.ac : dp, coordinate_compression, prefix_sum, sweeping, geometry
작성자 풀이 : dp, coordinate_compression, prefix_sum, sweeping, geometry, segtree(lazyprop)
풀이
원점에서 쏘는 직선의 기울기를 0에서 쭉 증가시킨다고 해보자. 그러면 직선이 레이저에 맞는 기울기가 구간으로 나타난다는 사실을 관찰할 수 있고, 이를 통해 dp를 할 수 있으며 이 때 필요한 값들을 레이지세그/imos를 이용해 전처리해주면 된다.
solved.ac 티어
20240213 기준 : Diamond V (μ = D5 - 0.01, σ = 0.55)
알고리즘 분류
solved.ac : segtree
작성자 풀이 : segtree, priority_queue
풀이
각 정사각형은 사선 방향의 직선 위에 있다는 사실을 관찰할 수 있고, 각 사선마다 독립적으로 문제를 해결할 수 있다. 각 사선에서 카운팅은 적당한 자료구조나 정렬을 이용해서 해줄 수 있다.
solved.ac 티어
20240215 기준 : Platinum I (μ = P1 + 0.17, σ = 0.40)
알고리즘 분류
solved.ac : dp, greedy, priority_queue
작성자 풀이 : dp, priority_queue
풀이
섭태5를 각 dp마다 파라메트릭 서치 속 이분탐색으로 풀어서 해결할 수 있다.
이때 답의 단조증가성을 이용하면 이분탐색을 굳이 하지 않아도 됨을 관찰할 수 있으며, pq에 증가량을 넣고 증가량이 작은 것부터 빼면서 구슬 하나의 공간을 확보해주는 느낌으로 풀어줄 수 있다.
solved.ac 티어
20240214 기준 : Gold II (μ = G2 - 0.40, σ = 0.53)
알고리즘 분류
solved.ac : ad_hoc
작성자 풀이 : 2-sat
풀이
원래 애드 혹 문제인데 뒤집는 조건을 이용해서 2-sat으로 간신히 풀 수 있다.
왜 굳이 2-sat으로 풀었냐면 선발고사 문제는 다 플래티넘 이상일 것이라고 생각해서 애드혹은 무조건 생각에서 배제했기 때문이다.
그냥 멍청해서 뚫었다고 치자.
처음으로 푼 투 스텝 문제이다.
solved.ac 티어
20240214 기준 : Platinum II (μ = P2 - 0.48, σ = 0.40)
알고리즘 분류
solved.ac : centroid, dfs/bfs, constructive
작성자 풀이 : centroid, bfs, constructive
풀이
대충 루트를 표시하고 depth가 같은 것끼리 최대한 이어주면 된다는 사실을 알 수 있다. 근데 루트를 아무거나 잡으면 안되고 K < N/2이므로 대충 센트로이드를 잡으면 될 것 같고 실제로도 된다. 그냥 사전지식 문제이다.
solved.ac 티어
20240214 기준 : Platinum II (μ = P2 + 0.39, σ = 0.87)
알고리즘 분류
solved.ac : greedy, tree_set
작성자 풀이 : greedy, tree_set
풀이
일단 다 챙긴다음 꽉 차면 비싼 것부터 버리자. 그 다음 이동할 때는 싼 것부터 쓰게 하면 된다. 이걸 구현하기 위해서 min, max 양쪽에서 빼는 pq가 필요한데 귀찮으니 set으로 해도 시간 안에 돈다.
solved.ac 티어
20240216 기준 : Platinum V (μ = P5 + 0.50, σ = 0.52)
알고리즘 분류
solved.ac : dp, game_theory, sprague_grundy
작성자 풀이 : dp, game_theory, sprague_grundy?
풀이
더미가 3개인 님 게임에서 각각 a, b, c개 있을 때 a ^ b ^ c가 0이면 후공이 이기고 아니면 선공이 이긴다는 건 (아마) 웰노운이다.
이때 최선의 전략으로 게임을 하면서 돌을 최대한 많이 가져가야 하므로 이기는 쪽은 자신이 승리하는 상태로 이동하면서 돌을 최대한 많이 가져가야 한다. 따라서 dp를 사용할 수 있으며 이 때 dp가 3차원이고 이길 때는 각 상태를 O(1)에 풀 수 있고 질 때는 O(N)에 풀 수 있는데 지는 상태가 O(N^2)개이므로 O(N^3)에 풀 수 있다.
와 번호 원주율
아레나 당시에 처음으로 제출했고 3분 차이로 퍼솔을 뺐겼다. 디버깅을 좀만 빨리 했으면 퍼솔이었을 텐데 아깝다.
solved.ac 티어
20240218 기준 : Platinum II (μ = P2 - 0.25, σ = 0.50)
알고리즘 분류
solved.ac : bruteforcing, simulation, prefix_sum
작성자 풀이 : bruteforcing, simulation, binary_search
풀이
일단 x, y가 독립적임을 관찰할 수 있다. 그러니 x좌표 풀이만 고려하고 y좌표는 똑같이 적용하자.
또한 x=0, 1, ... 10^5에 대해 모두 문제를 풀어 놓고 쿼리는 O(1)에 처리한다고 생각할 것이다. (구현의 편의를 위해서이다. 물론 이렇게 안했으면 3번째 제출 때 TLE가 안나서 퍼솔을 먹었을 수도 있다)
일단 dx가 양수라고 생각하자.
T = 10^9라고 생각하고 x=k에 i번째 UFO가 닿을 조건을 생각해보면 x[i], k가 dx[i]에서 합동이면 된다.
이제 각 dx에 대해 문제를 풀어줄 것인데, 이 때 중요한 것은 dx[i]가 클 수록 닿는 레이저 수가 감소한다는 것이다. 각 dx마다 최대 10^5/dx개 정도의 레이저에 맞는다. 즉 dx>300이면 닿는 레이저가 300개 정도라서 그냥 naive하게 봐줘도 문제 없다. 이제 dx < 300인 경우만 고려하자.
그래서 (dx, x mod dx) 쌍을 벡터같은 곳에 저장해두고 정렬한 후 이분탐색으로 한번에 처리해줄 수 있다. dx, x mod dx 모두 300 이하이므로 약 9만 개의 벡터만 있으면 된다.
음수는 좌표를 x := 10^5 - x로 변환한다음 dx를 양수로 만들면 비슷하게 처리해줄 수 있다.
