분류 전체보기
-
220924 문제 풀이 기록2022.09.25
-
220923 문제 풀이 기록2022.09.24
-
220922 문제 풀이 기록2022.09.23
-
220921 문제 풀이 기록2022.09.21
-
220919 문제 풀이 기록2022.09.19
-
220918 문제 풀이 기록2022.09.18
-
220917 문제 풀이 기록2022.09.18
-
220916 문제 풀이 기록2022.09.17
-
220915 문제 풀이 기록2022.09.15
-
220913 문제 풀이 기록2022.09.13
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 |
220918 문제 풀이 기록
P4 | 5914 - Cow Photography
풀이 시간: 1시간
시도 횟수: 2회
체감 난이도: P4
풀이 쓸 의향: 中
풀이
어떤 두 숫자에 대해, 상대적인 위치가 세 번 이상 동일한 위치관계에 있다면 해당 상대적인 순서를 유지하며 정렬하기. 즉, cmp 함수에서 int a, int b의 상대적 위치를 5번 비교하여 a가 b 왼쪽에 3번 이상 있었으면 a가 왼쪽, 아니면 b가 왼쪽에 있도록 정렬시키기
여담: 와.... 와...... 어떻게 문제를 이렇게 만들지...?? 싶은 개쩌는 문제... 솔직히 머리속에 위상정렬만 막 떠오르고 못풀겠어서 태그랑 코드 길이 슬쩍 봤다가 상당히 의아했었는데, 풀이 떠올리고 실소가 나왔음... sort의 cmp 함수는 서로 다른 두 수 사이의 상대적인 위치관계를 나타낸다는 사실을 각인시켜준 문제. 정말 대단한 문제다.
솔직히 풀이 쓸 의향이 上이어야 하지만, 풀이가 워낙에 단순한지라... 그리고 힌트를 쓸만한게 딱히 없어서... 일단 中으로..
'PS > 풀이 기록장' 카테고리의 다른 글
| 220921 문제 풀이 기록 (0) | 2022.09.21 |
|---|---|
| 220919 문제 풀이 기록 (0) | 2022.09.19 |
| 220917 문제 풀이 기록 (0) | 2022.09.18 |
| 220916 문제 풀이 기록 (0) | 2022.09.17 |
| 220915 문제 풀이 기록 (0) | 2022.09.15 |
220917 문제 풀이 기록
P4 | 5922 - Above the Median
풀이 시간: 약 30분
시도 횟수: 1회
체감 난이도: P4
풀이 쓸 의향: 下
풀이
X 이상을 1, X 미만을 -1로 두고 부분합의 개수 control하기.
무조건 부분합은 -n~n까지이므로, 일단 초기에는 부분합이 0 이상인 개수 counting한 뒤 시작점이 1번인것부터 하나씩 날리면서 개수 counting 한 합 구하기.
여담: 너무 안보이길래 태그 슬쩍 보고 풀었다... "아니 대체 h가 10억 제한인데 중간값을 어떻게 구해" 부터 시작하는 뇌절을 빠르게 끊어주는 핵심 아이디어를 토대로 그나마 수월하게 푼듯하다. 역시 중앙값을 구하기가 그렇게 쉬울리가 없지..
'PS > 풀이 기록장' 카테고리의 다른 글
| 220919 문제 풀이 기록 (0) | 2022.09.19 |
|---|---|
| 220918 문제 풀이 기록 (0) | 2022.09.18 |
| 220916 문제 풀이 기록 (0) | 2022.09.17 |
| 220915 문제 풀이 기록 (0) | 2022.09.15 |
| 220913 문제 풀이 기록 (0) | 2022.09.13 |
220916 문제 풀이 기록
P5 | 10651 - Cow Jog
풀이 시간: 약 30분
시도 횟수: 2회
체감 난이도: P5
풀이 쓸 의향: 下
풀이
입력값 쿼리인 입력 a, b에 endpoint e=a + b*t에 대해, multiset 및 lower_bound를 활용하여 지금까지 등장한 endpoint 중 현재 endpoint보다 작은 최대인 endpoint 없애고 현재 endpoint 넣기. 정답은 multiset size
여담: 태그를 보니까 LIS(nlogn)이던데, 생각해보니까 그렇게 풀어도 되긴 할듯 하다...만 위 풀이가 구현이 너무 쉽기 때문에 위 풀이로 풀었음. 처음에는 pq로 가장 작은 값 빼내려고 했는데, 틀리고 나서 생각해보니까 그러면 안됐음. 어쩐지 너무 쉽더라...
P3 | 10650 - Marathon
풀이 시간: 45분
시도 횟수: 4회
체감 난이도: P3(구현 많음)
풀이 쓸 의향: 下
풀이
합 segtree로 I부터 J까지 거리를, 최댓값 segtree로 I+1부터 J-1까지 각 checkpoint를 skip할때의 최대 이득을 관리하며 쿼리 수행하기
여담: 하나의 checkpoint를 수정해도 전체에서 자기 자신과 주변 두 개의 checkpoint에만 영향이 간다는 아이디어를 활용하는 문제. 처음에는 총 거리를 부분합으로 구현했다가 틀렸고, 나머지 두번은 sum segtree를 더할때 max segtree와는 다르게 i==1일때는 안더하고 i==n일때는 더해야 한다는 점을 망각했다가 틀림.
USACO 2014 December Gold 풀이 끝!
'PS > 풀이 기록장' 카테고리의 다른 글
| 220918 문제 풀이 기록 (0) | 2022.09.18 |
|---|---|
| 220917 문제 풀이 기록 (0) | 2022.09.18 |
| 220915 문제 풀이 기록 (0) | 2022.09.15 |
| 220913 문제 풀이 기록 (0) | 2022.09.13 |
| 220912 문제 풀이 기록 (0) | 2022.09.13 |
220915 문제 풀이 기록
P5 | 23034 - 조별과제 멈춰!
풀이 시간: 총 1시간 20분
시도 횟수: 무수히 많이
체감 난이도: P5
풀이 쓸 의향: 下
풀이
MST 만들고 두 사람 사이의 간선 중 최대값 빼고 출력
여담: 어제부터 오늘까지 이거 왜 안되지... 하면서 끙끙대고 있었는데, 별 이상한데서 실수를 하고 있었는데 자꾸 MST 구현에서 틀린줄 알고 삽질하고 있었다.... 아니 MST 구현 많이 해봤으면서 왜 MST 구현에서 실수를 찾고 있는지...... ;(
'PS > 풀이 기록장' 카테고리의 다른 글
| 220917 문제 풀이 기록 (0) | 2022.09.18 |
|---|---|
| 220916 문제 풀이 기록 (0) | 2022.09.17 |
| 220913 문제 풀이 기록 (0) | 2022.09.13 |
| 220912 문제 풀이 기록 (0) | 2022.09.13 |
| 220911 문제 풀이 기록 (0) | 2022.09.11 |
220913 문제 풀이 기록
G4 | 1967 - 트리의 지름
풀이 시간: X
시도 횟수: 1회
체감 난이도: G4
풀이 쓸 의향: 下
풀이
1번 노드에서 가장 멀리 있는 x번 노드, x번 노드에서 가장 멀리 있는 y번 노드 두 노드를 이은 거리가 지름임
여담: 바로 아래 적을 문제 풀기 전에 겸사겸사 제출함.
P5 | 13016 - 내 왼손에는 흑염룡이 잠들어 있다
풀이 시간: 약 1시간 + a
시도 횟수: 1회
체감 난이도: P5
풀이 쓸 의향: 下
풀이
트리 지름의 말단 노드 두개 잡고 2N번 순회하면서 최대 길이 찾기
여담: 어제 코포하기 전에 잠깐 보다가 코포시간되서 그냥 코포치러 가느라 못풀었던 문제. 트리의 지름 쓰는 문제인건 알 수 있었는데 아직도 트리의 지름 문제를 안풀었어서 트리의 지름 구하는 법을 모르고 있었다.
G5 | 15681 - 트리와 쿼리
풀이 시간: 10분
시도 횟수: 1회
체감 난이도: G5
풀이 쓸 의향: 下
풀이
그냥 트리 순회하면서 값 저장하기
여담: Tree DP를 거의 안풀었던 것 같아서 잡아봤는데, 이게 DP인가....? 싶었음.
P4 | 17082 - 쿼리와 쿼리
풀이 시간: 아이디어 1시간 + 디버깅 2시간
시도 횟수: 무수히 많음
체감 난이도: P4
풀이 쓸 의향: 下
풀이
구간은 그리디하게 정렬한 뒤 앞에서부터 잡으면 되고, 구간 병합한 뒤에 주어지는 쿼리에 따라 값 바꿔끼며 최대값 관리하기. multiset 쓰면 편리함
여담: 오늘 이 문제 때문에 시간 너무 많이 날렸는데... 왜 자꾸 segfault 뜨는지 모르겠어서 무지성 제출 박으니까 갑자기 됐다. 아니 근데 왜 됐지??
참고로 풀이할때 세그트리를 썼었는데, 태그를 보아하니 세그트리는 필요 없었던 모양...
P4 | 10649 - 프리스비
풀이 시간: 약 1시간 + 20분
시도 횟수: 1회
체감 난이도: P4
풀이 쓸 의향: 中
풀이
(키+무게) 내림차순으로 정렬 후, (총 무게) - (키 + 무게) 값으로 정답 구하기. N<=20이므로 비트마스킹으로 모든 집합 순회하면서 브루트 포싱하면 풀림.
여담: 예전에 한번 봤다가 못풀겠어서 버려뒀는데, 마침 랜덤으로 돌렸는데 나오길래 풀어보니까... 20분만에 금방 풀이가 나왔다. 그리디가 참 한번 막히면 너무 막히고, 한번 잘풀리면 너무 잘풀리는 느낌이다.
P5 | 2123 - 인간 탑 쌓기
풀이 시간: 1시간 + X
시도 횟수: 2회 + 1회
체감 난이도: P5
풀이 쓸 의향: 中
풀이
(키+무게) 내림차순으로 정렬 후, (키 + 무게) - (총 무게) 값으로 정답 구하기.
여담: 프리스비 문제 풀다가, 뭔가 비슷한 문제를 저번에 시도했다가 틀렸던 기억이 나서 찾아보니 있었다. 간단한 처리를 제외하면 거의 동일한 문제지만, 그래도 프리스비 쪽이 더 어렵지 않나 싶다. 그보다 프리스비랑 인간 탑 쌓기 둘 다 예전에 풀다가 던졌던 문젠데, 오늘 하루 종일 백준만 풀어서 머리가 잘돌아가나 싶다.
'PS > 풀이 기록장' 카테고리의 다른 글
| 220916 문제 풀이 기록 (0) | 2022.09.17 |
|---|---|
| 220915 문제 풀이 기록 (0) | 2022.09.15 |
| 220912 문제 풀이 기록 (0) | 2022.09.13 |
| 220911 문제 풀이 기록 (0) | 2022.09.11 |
| 220910 문제 풀이 기록 (0) | 2022.09.11 |