220924 문제 풀이 기록
P4 | 9569 - No Change
풀이 시간: 1시간
시도 횟수: 3회
체감 난이도: P3
풀이 쓸 의향: 下
풀이
대놓고 bitfield DP + 약간의 이분 탐색
여담: 처음에는 DP 설계 자체를 엉망으로 해서 -1, 이분 탐색 안해서 -1 후 해결.
for (int i=0; i< (1 << k); i++) 에서 i ^ s 하는것만으로도 해결 가능했는데, 비트마스킹에 익숙하지 않아서 그 사실을 모르고 그냥 builtin__popcount로 1의 개수에 해당하는 2차원 벡터를 차례대로 순회하도록 하여 해결했다.
문제 풀이 자체는 재밌었지만, 딱히 풀이를 쓸 건덕지가 없어서 풀이 쓸 의향은 下로 준다.
'PS > 풀이 기록장' 카테고리의 다른 글
| 221001 문제 풀이 기록 (0) | 2022.10.02 |
|---|---|
| 220925 문제 풀이 기록 (0) | 2022.09.26 |
| 220923 문제 풀이 기록 (0) | 2022.09.24 |
| 220922 문제 풀이 기록 (0) | 2022.09.23 |
| 220921 문제 풀이 기록 (0) | 2022.09.21 |
220923 문제 풀이 기록
P5 | 5828 - Fuel Economy
풀이 시간: 무려 2시간
시도 횟수: 3회
체감 난이도: 분하게도 P5
풀이 쓸 의향: 下
풀이
i번째 다음으로 작으며 g 범위 안에 있는 다음 위치 nxt[i]를 잘 생각하며 계산하기. nxt[i]가 존재하면 해당 위치까지만 가면 되고, 존재하지 않으면 g만큼 다 사야 함.
여담: Monotone stack을 사용하는 문제였는데, 구현에서 너무 애를 많이 먹어버렸다. 처음에는 deque로 구현해보려 했는데, 구현중 뇌절이 너무 심하게 와서 여러번 틀리고 반례를 너무 늦게 찾아버렸다... 태그 힌트 보고 바로 stack으로 바꿔서 해결하긴 했는데, stack 구현을 n부터 1까지 역순으로 해주는 처리가 인상깊었다.
P4 | 11962 - Counting Haybales
풀이 시간: 35분
시도 횟수: 1회
체감 난이도: 어쩔수 없이 P4
풀이 쓸 의향: 下
풀이
min / sum lazy seg를 구현할 수 있는지를 묻는 문제.
여담: 이번에도 USACO p4 랜덤을 돌렸는데 이런게 나와버렸다. 음... 다음부터는 다시는 안나왔으면 좋겠다. 이런 문제들 자체가 싫다는건 아니고, 그냥 너무 날먹하는 기분밖에 안들어서...
'PS > 풀이 기록장' 카테고리의 다른 글
| 220925 문제 풀이 기록 (0) | 2022.09.26 |
|---|---|
| 220924 문제 풀이 기록 (0) | 2022.09.25 |
| 220922 문제 풀이 기록 (0) | 2022.09.23 |
| 220921 문제 풀이 기록 (0) | 2022.09.21 |
| 220919 문제 풀이 기록 (0) | 2022.09.19 |
220922 문제 풀이 기록
P3 | 1395 - 스위치
풀이 시간: X
시도 횟수: 1회
체감 난이도: P3
풀이 쓸 의향: 下
풀이
레이지 세그 연습 문제
여담: USACO 랜덤 돌렸더니 나왔길래 레이지 세그 연습하는셈 치고 풀었음. 근데 생각보다 구현에 애를 먹어서 다른 코드들 참고하며 풀었음... 사실상 내가 푼 게 아닌 느낌이긴 하지만 레이지 세그 연습용으로는 괜찮았다.
P4 | 15587 - Cow at Large (Gold)
풀이 시간: 30분
시도 횟수: 2회
체감 난이도: P4
풀이 쓸 의향: 中
풀이
BFS와 DFS를 잘 쓰까서, DFS로는 리프 노드에서 다른 모든 노드로 가는 최소 거리를, BFS로는 시작 위치에서 다른 모든 노드로 가는 최소 거리를 구한 뒤에 노드 개수 세주기
여담: 풀이를 생각하기엔 까다롭지는 않았으나, 구현을 어떤 방식으로 해야 할 지 고민을 하게 만든 문제. 풀이 과정도 재밌고 구현도 재밌었다.
P2 | 12008 - 262144
풀이 시간: 50분
시도 횟수: 2회
체감 난이도: P2
풀이 쓸 의향: 上
풀이
연속한 동일한 수의 그룹이 짝수개라면 그냥 그리디하게 합쳐주면 되고, 홀수개라면 배열을 두개로 쪼개서 왼쪽 / 오른쪽 나눠서 계속 계산해주기.
여담: 풀이를 생각하고, 해당 풀이의 정당성을 증명하고, 해당 풀이의 시간/공간 복잡도가 시간/메모리 제한 안에 부합하는지 확인하고, 적절하게 구현하기까지 과정이 즐거웠다. 특히 문제도 짧고 간결해 이해하기도 쉬웠다.
근데 태그가 내 생각과는 다르게 박혀 있길래 다른 사람들의 풀이도 봤는데, 관찰까지는 다들 비슷했으나 나는 단순 구현으로, 다른 사람들은 여러 테크닉을 응용한 dp정도로 푼 모양이다. 그 풀이들도 다들 훌륭한 것 같다.
P5 | 1572 - 중앙값
풀이 시간: 15분
시도 횟수: 1회
체감 난이도: P5
풀이 쓸 의향: 下
풀이
사탕상자 문제처럼 sum seg에 이분탐색 구현하기
여담: 자기 전 마지막 한 문제 풀고 가려고 랜덤 돌렸는데 나왔다... 그냥 연습삼아 슥 풀고 감.
'PS > 풀이 기록장' 카테고리의 다른 글
| 220924 문제 풀이 기록 (0) | 2022.09.25 |
|---|---|
| 220923 문제 풀이 기록 (0) | 2022.09.24 |
| 220921 문제 풀이 기록 (0) | 2022.09.21 |
| 220919 문제 풀이 기록 (0) | 2022.09.19 |
| 220918 문제 풀이 기록 (0) | 2022.09.18 |
220921 문제 풀이 기록
G1 | 18262 - Milk Pumping
풀이 시간: 20분
시도 횟수: 1회
체감 난이도: G2
풀이 쓸 의향: 下
풀이
f 제한 1이상 ~ 1000이상까지 1000번 다익스트라 돌리기
여담: 원래 P5였는데 G2 투표해서 G1으로 만들었음. 쩝,,,
P4 | 5851 - Cow Lineup
풀이 시간: 1시간
시도 횟수: 1회
체감 난이도: P3
풀이 쓸 의향: 中
풀이
값 압축 후, 투 포인터로 서로 다른 숫자 개수가 K+1 이하로 유지하며 구간 체크하기.
여담: [l, r] 구간 안에서 서로 다른 숫자 개수를 세그트리로 구할 수 있지 않을까? 하는 생각에 좀 오래 말렸던 것 같음. 근데 찾아보니까 되는 풀이가 맞긴 한데... 어,,,,, 나중에 알아보도록 하자...
P4 | 5852 - Island Travels
풀이 시간: 40분
시도 횟수: 3회
체감 난이도: P4
풀이 쓸 의향: 下
풀이
일단 각 섬들의 번호를 기록한 뒤에, 각 섬에서 다른 섬으로 갈 때 필요한 최소 수영 거리를 계산하고, 해당 값을 바탕으로 시작점 N개에 대해 외판원 순회 문제처럼 비트필드 dp로 최솟값 찾기
여담: 문제 풀이가 바로 떠올라서 "그는 신인가???" 했었는데 구현에서만 35분을 쓰면서 개같이 멸망!! 풀이 자체는 참 어려울 것 없는데 구현해야 할 것들이 너무 많아서 실수했으면 그대로 디버깅의 늪에 빠져 헤멜뻔 했는데, 다행히 별 것 아닌 실수들만 해서 살았다.
'PS > 풀이 기록장' 카테고리의 다른 글
| 220923 문제 풀이 기록 (0) | 2022.09.24 |
|---|---|
| 220922 문제 풀이 기록 (0) | 2022.09.23 |
| 220919 문제 풀이 기록 (0) | 2022.09.19 |
| 220918 문제 풀이 기록 (0) | 2022.09.18 |
| 220917 문제 풀이 기록 (0) | 2022.09.18 |
220919 문제 풀이 기록
P3 | 5915 - Simplifying the Farm
풀이 시간: 1시간 30분
시도 횟수: 무수히 많음
체감 난이도: P3
풀이 쓸 의향: 中
풀이
크루스칼 MST로 조지면서 가능한 연결 개수 / 연결한 간선 개수 체크하면서 곱해주기. 어떤 MST 하나를 만들 때 사용되는 간선의 가중치 별 개수는 동일하다는 점을 이용함.
여담: 처음에는 Prim으로 짜려다가 너무 복잡해져서 Kruskal로 틀었는데, long long 안해줘서 여러번 틀리고 disjoint set 이상하게 구현해서 자꾸 틀림...
'PS > 풀이 기록장' 카테고리의 다른 글
| 220922 문제 풀이 기록 (0) | 2022.09.23 |
|---|---|
| 220921 문제 풀이 기록 (0) | 2022.09.21 |
| 220918 문제 풀이 기록 (0) | 2022.09.18 |
| 220917 문제 풀이 기록 (0) | 2022.09.18 |
| 220916 문제 풀이 기록 (0) | 2022.09.17 |