PS
-
221011 문제 풀이 기록2022.10.11
-
221008 문제 풀이 기록2022.10.08
-
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
221011 문제 풀이 기록
P4 | 11993 - Circular Barn (Gold)
풀이 시간: 1시간
시도 횟수: 2회
체감 난이도: P4
풀이 쓸 의향: 中
풀이
가장 왼쪽에 근접한 원소를 고르는 것이 최적이다.
여담: 투포인터 구현 실수해서 -1.
다른 사람 코드 보고 알았는데, queue로 하면 훨씬 쉬움... 아니 어떻게 이 생각을 못하지;;;;;;;
'PS > 풀이 기록장' 카테고리의 다른 글
| 221014 ~ 221017 문제 풀이 기록 (0) | 2022.10.17 |
|---|---|
| 221012 문제 풀이 기록 (0) | 2022.10.12 |
| 221008 문제 풀이 기록 (0) | 2022.10.08 |
| 221006 문제 풀이 기록 (0) | 2022.10.06 |
| 221004 문제 풀이 기록 (0) | 2022.10.04 |
221008 문제 풀이 기록
P4 | 16764 - Cowpatibility
풀이 시간: 1시간
시도 횟수: 4회
체감 난이도: P4
풀이 쓸 의향: 下
풀이
map<vector<int>, int>로 관리하면서 포함/배제의 원리 사용하여 bitmasking 하기
여담: 이런 것도 되는지는 이번에 처음 알았다... 뭐지 이 문제???
'PS > 풀이 기록장' 카테고리의 다른 글
| 221012 문제 풀이 기록 (0) | 2022.10.12 |
|---|---|
| 221011 문제 풀이 기록 (0) | 2022.10.11 |
| 221006 문제 풀이 기록 (0) | 2022.10.06 |
| 221004 문제 풀이 기록 (0) | 2022.10.04 |
| 221003 문제 풀이 기록 (0) | 2022.10.04 |
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 |