PS/풀이 기록장
-
221006 문제 풀이 기록2022.10.06
-
221004 문제 풀이 기록2022.10.04
-
221003 문제 풀이 기록2022.10.04
-
221002 문제 풀이 기록2022.10.02
-
221001 문제 풀이 기록2022.10.02
-
220925 문제 풀이 기록2022.09.26
-
220924 문제 풀이 기록2022.09.25
-
220923 문제 풀이 기록2022.09.24
-
220922 문제 풀이 기록2022.09.23
-
220921 문제 풀이 기록2022.09.21
221006 문제 풀이 기록
P4 | 6142 - Gourmet Grazers
풀이 시간: 20분
시도 횟수: 1회
체감 난이도: P4 하위권
풀이 쓸 의향: 下
풀이
각각의 pair 배열을 green 내림차순 정렬 후, 마트 재고 중 해당 greenness보다 큰 grenness를 가진 것들 중 비용이 최소 비용 이상인 가장 작은 물품 구매하기. multiset lower_bound로 쉽게 해결 가능.
여담: 풀이가 빠르게 떠올라서 쉽게 풀었다.
P4 | 14449 - Balanced Photo
풀이 시간: 15분
시도 횟수: 1회
체감 난이도: P4
풀이 쓸 의향: 下
풀이
값 압축을 통해 h_i를 [1, N] 사이 범위로 바꿔준 뒤, 순서대로 [해당 값, N] 사이의 원소의 개수를 segtree로 세어주며 l_i, r_i 구하기
여담: 값 압축 안하고 키 내림차순 정렬 후 세그트리를 써도 풀린다. 세그트리에 순서를 넣는다는 아이디어보다 압축된 값을 넣는다는 아이디어가 더 빠르게 떠올라서 그냥 값 압축 세그트리를 쓰긴 했지만...
뭔가 두 문제 다 너무 빨리 풀어서 날먹한 기분... 뭐지?
'PS > 풀이 기록장' 카테고리의 다른 글
| 221011 문제 풀이 기록 (0) | 2022.10.11 |
|---|---|
| 221008 문제 풀이 기록 (0) | 2022.10.08 |
| 221004 문제 풀이 기록 (0) | 2022.10.04 |
| 221003 문제 풀이 기록 (0) | 2022.10.04 |
| 221002 문제 풀이 기록 (0) | 2022.10.02 |
221004 문제 풀이 기록
P4 | 1209 - 단조 수열 만들기
풀이 시간: 1시간
시도 횟수: 7회
체감 난이도: P3
풀이 쓸 의향: 中
풀이
모든 B의 원소는 A의 원소만으로 이루어져도 최적값을 찾을 수 있다는 사실을 증명한 뒤, N^2 DP로 풀기
여담: 범위가 Long Long 범위인데 dp값 초기화를 INT_MAX로 조져버리는 바람에 20분이나 낭비했다... 요즘 자꾸 왜이러지 진짜;
'PS > 풀이 기록장' 카테고리의 다른 글
| 221008 문제 풀이 기록 (0) | 2022.10.08 |
|---|---|
| 221006 문제 풀이 기록 (0) | 2022.10.06 |
| 221003 문제 풀이 기록 (0) | 2022.10.04 |
| 221002 문제 풀이 기록 (0) | 2022.10.02 |
| 221001 문제 풀이 기록 (0) | 2022.10.02 |
221003 문제 풀이 기록
P4 | 14459 - 소가 길을 건너간 이유 11
풀이 시간: X
시도 횟수: 2회
체감 난이도: X
풀이 쓸 의향: 下
풀이
9*N LIS 돌리는데, pair<int, int>에서 l은 오름차순, r을 내림차순으로 정렬한 뒤 lis를 돌리자.
여담: 답을 슬쩍 보고 풀어서... LIS를 이렇게 활용할 수도 있구나 배워가는 시간이었다.
'PS > 풀이 기록장' 카테고리의 다른 글
| 221006 문제 풀이 기록 (0) | 2022.10.06 |
|---|---|
| 221004 문제 풀이 기록 (0) | 2022.10.04 |
| 221002 문제 풀이 기록 (0) | 2022.10.02 |
| 221001 문제 풀이 기록 (0) | 2022.10.02 |
| 220925 문제 풀이 기록 (0) | 2022.09.26 |
221002 문제 풀이 기록
P4 | 14458 - 소가 길을 건너간 이유 10
풀이 시간: 1시간
시도 횟수: 6회
체감 난이도: P3
풀이 쓸 의향: 下
풀이
segtree로 일단 초기 쌍 세어준 다음에, 왼쪽 올리기 & 오른쪽 올리기 하면 왼쪽 & 오른쪽 내림차순 정렬한 후에 순서대로 올려주면서 최솟값 찾기
여담: 잘 풀어놓고 오른쪽만 올려도 되겠지 하는 안일한 생각에 30분을 추가로 날려버린 나... 어쩌면 멍청이일지도??
'PS > 풀이 기록장' 카테고리의 다른 글
| 221004 문제 풀이 기록 (0) | 2022.10.04 |
|---|---|
| 221003 문제 풀이 기록 (0) | 2022.10.04 |
| 221001 문제 풀이 기록 (0) | 2022.10.02 |
| 220925 문제 풀이 기록 (0) | 2022.09.26 |
| 220924 문제 풀이 기록 (0) | 2022.09.25 |
221001 문제 풀이 기록
P4 | 14463 - 소가 길을 건너간 이유 9
풀이 시간: 50분
시도 횟수: 3회
체감 난이도: P4
풀이 쓸 의향: 下
풀이
시작점, 끝점을 시작점 기준으로 정렬해두고 세그트리로 개수 세기
여담: 문제 처음에 잘못 읽고 두번 박았음... 겹치는 경로를 가지는 소의 수를 세는건줄 알았는데 겹치는 쌍의 수를 세는거였단걸 50분 지나고 나서 깨달아버림 ;(
'PS > 풀이 기록장' 카테고리의 다른 글
| 221003 문제 풀이 기록 (0) | 2022.10.04 |
|---|---|
| 221002 문제 풀이 기록 (0) | 2022.10.02 |
| 220925 문제 풀이 기록 (0) | 2022.09.26 |
| 220924 문제 풀이 기록 (0) | 2022.09.25 |
| 220923 문제 풀이 기록 (0) | 2022.09.24 |
220925 문제 풀이 기록
P3 | 5896 - 효율적으로 소 사기
풀이 시간: 약 1시간 30분 + a
시도 횟수: 4회
체감 난이도: P3
풀이 쓸 의향: 下
풀이
쿠폰 오름차순 / 일반가 오름차순 각각의 pq 두개 만들어두고, 쿠폰 오름차순부터 차례대로 보면서 최소값으로만 고르기
여담: pq 심화 문제였는데, 너무 헤맸다... 너무 그리디를 다른 방식으로만 생각한 것 같다.
P3 | 5910 - Mountain Climbing
풀이 시간: 1시간 20분
시도 횟수: 3회
체감 난이도: P3
풀이 쓸 의향: 下
풀이
down>=up과 down<up 두 가지로 나눠보면 down>=up인것 우선으로, down>=up이면 up 오름차순 / down<up이면 down 내림차순 정렬하여 둔 것이 최적이라는 사실을 증명한 뒤에 구현하기
여담: 대체 이걸 어떻게 생각해야 할지 감도 안와서 문제 풀다 잠깐 쉬고 와서 다시 풀었다. 오늘 푼 그리디 두 문제 모두 내가 지금까지 봐왔던 그리디랑은 조금 다른 형태의 그리디였는데, 한 관찰에서 20분 이상 생각하지 말고 20분 넘게 관찰하다가 해당 방향으로 관찰이 힘들면 다른 방식으로 관찰해야겠다. 이 문제를 풀 때는 반드시 down이 연속적으로 되면 맨 앞의 up + sum(down)일 것인데, 이때 up을 어떻게 구할지 내지는 down이 어떻게 연속이 될 수 있을지를 보고 있었는데, 결과적으로는 아예 쓸데없는 관찰이었다.
'PS > 풀이 기록장' 카테고리의 다른 글
| 221002 문제 풀이 기록 (0) | 2022.10.02 |
|---|---|
| 221001 문제 풀이 기록 (0) | 2022.10.02 |
| 220924 문제 풀이 기록 (0) | 2022.09.25 |
| 220923 문제 풀이 기록 (0) | 2022.09.24 |
| 220922 문제 풀이 기록 (0) | 2022.09.23 |
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 |