PS/풀이 기록장
-
220919 문제 풀이 기록2022.09.19
-
220918 문제 풀이 기록2022.09.18
-
220917 문제 풀이 기록2022.09.18
-
220916 문제 풀이 기록2022.09.17
-
220915 문제 풀이 기록2022.09.15
-
220913 문제 풀이 기록2022.09.13
-
220912 문제 풀이 기록2022.09.13
-
220911 문제 풀이 기록2022.09.11
-
220910 문제 풀이 기록2022.09.11
-
220909 문제 풀이 기록2022.09.10
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 |
220912 문제 풀이 기록
*800 | 1702A. Round Down the Price
풀이 시간: 무려 +12분
시도 횟수: 무려 2회
체감 난이도: B3
풀이 쓸 의향: 下
풀이
- while (ans*10 <= n) ans*=10;
- cout << n-ans << "\n";
여담: 문제를 잘못읽고 냈다가 안보고 B풀고 나서 다시품
*800 | 1702B. Polycarp Writes a String from Memory
풀이 시간: 10분
시도 횟수: 1회
체감 난이도: B1
풀이 쓸 의향: 下
풀이
단순 브루트포싱 및 구현.
여담: string 관련 구현을 너무 못하는...
*1100 | 1702C. Train and Queries
풀이 시간: 13분
시도 횟수: 1회
체감 난이도: S1
풀이 쓸 의향: 下
풀이
map으로 가장 왼쪽 / 오른쪽 저장해놓은 상태에서 풀기
여담: 단순 map 구현 문젠데 생각보다 오래걸려버림 ㅠ
*1000 | 1702D. Not a Cheap String
풀이 시간: 5분
시도 횟수: 1회
체감 난이도: S3
풀이 쓸 의향: 下
풀이
greedy하게 가장 높은 비용의 letter 하나씩 빼기
여담: C>>D Forces..
*1600 | 1702E. Split Into Two Sets
풀이 시간: 30분
시도 횟수: 2회
체감 난이도: G3
풀이 쓸 의향: 中
풀이
그래프로 구현하여 그래프 노드 개수가 전부 짝수면 YES, 아니면 NO
여담: 참신한 문제
*1700 | 1702F. Equate Multisets
풀이 시간: 40분
시도 횟수: 4회
체감 난이도: G3
풀이 쓸 의향: 下
풀이
배열 a의 원소가 모두 홀수가 될때까지 전부 2로 나눠준 뒤, b를 계속 나누면서 a의 원소가 되는지 확인. multiset 쓰면 편함.
여담: a의 원소가 짝수면 무조건 되는줄 착각하고 -1, multiset 1일때 고려 안해서 -2;
*800? | 1729A. Two Elevators
풀이 시간: 무려 6분
시도 횟수: 무려 2회
체감 난이도: B3
풀이 쓸 의향: 下
풀이
단순 구현
여담: 문제 잘못 읽고 -1;
*800? | 1729B. Decode String
풀이 시간: 7분
시도 횟수: 1회
체감 난이도: B1
풀이 쓸 의향: 下
풀이
단순 구현
여담: string 구현이 좀 귀찮음
*1000? | 1729C. Jumping on Tiles
풀이 시간: 무려 20분
시도 횟수: 무려 2회
체감 난이도: S4
풀이 쓸 의향: 下
풀이
(시작점, 끝점)이 오름차순이면 오름차순 모든 letter 순회, 내림차순이면 내림차순으로 순회;
여담: 내림차순 처리 안해놓고 왜틀렸는지 몰라서 시간 좀 많이 날림...
*1100? | 1729D. Friends and the Restaurant
풀이 시간: 10분
시도 횟수: 1회
체감 난이도: S1??
풀이 쓸 의향: 下
풀이
[갖고 있는 돈 - 내야 하는 돈] 오름차순 정렬해두고 투포인터 그리디
여담: 풀이 시간 < 구현 시간 < 문제 이해 시간
*1600???? | 1729E. Guess the Cycle Size
풀이 시간: 50분!!!!!!!
시도 횟수: 무려 12회;
체감 난이도: X
풀이 쓸 의향: 下
풀이
(1 2) / (2 1), (2 3) / (3 2) ... 같이 (a b) (b a) 번갈아 쿼리 날리면 1/2^25 확률로 틀리니 사실상 맞음
여담: 이건... 쉬운데.... 뭐지 이게;
*1800 | 1729F. Kirei and the Linear Function
풀이 시간: 1시간
시도 횟수: 무려? 6회
체감 난이도: G1
풀이 쓸 의향: 下
풀이
(a*b)%c = ((a%c) * (b%c))%c, (a+b)%c = (a%c + b%c)%c이며, 9로 나눈 나머지는 항상 모든 자리수의 합을 9로 나눈 나머지와 같다는 사실을 이용하자.
부분합을 활용해 각 테스트케이스마다 각 시작점에서의 substring을 9로 나눈 나머지를 알 수 있고, 나머지 값은 0부터 8까지이므로 각 쿼리마다 9^2 순회 돌면서 확인하면 됨.
여담: 초기화를 쿼리 while안이 아니라 TC while안에서 바꿔주는 기열찐빠짓을 저지르는 바람에 시간 안에 못풀었음....
아 아직도 화나네 ㅋㅋㅋㅋㅋㅋㅋ
'PS > 풀이 기록장' 카테고리의 다른 글
| 220915 문제 풀이 기록 (0) | 2022.09.15 |
|---|---|
| 220913 문제 풀이 기록 (0) | 2022.09.13 |
| 220911 문제 풀이 기록 (0) | 2022.09.11 |
| 220910 문제 풀이 기록 (0) | 2022.09.11 |
| 220909 문제 풀이 기록 (0) | 2022.09.10 |
220911 문제 풀이 기록
P5 | 17489 - 보물 찾기
풀이 시간: 40분
시도 횟수: 2회
체감 난이도: G1 상위권
풀이 쓸 의향: 下
풀이
(시작점, 끝점)으로 구성되는 그래프를 형성한 뒤에, (1, 1)에서 시작하는 점 중 가장 멀리 있는 점 출력. 이때, 사이클이 생기면 -1 출력.
여담: 솔직히 P5는 아닌것 같다 싶긴 했지만, 그래도 구현이 조금 까다로워서... P5 받을만도 하지 않나 싶었다.
오늘은 다른 프로젝트를 진행하느라 문제는 이거 하나만...
'PS > 풀이 기록장' 카테고리의 다른 글
| 220913 문제 풀이 기록 (0) | 2022.09.13 |
|---|---|
| 220912 문제 풀이 기록 (0) | 2022.09.13 |
| 220910 문제 풀이 기록 (0) | 2022.09.11 |
| 220909 문제 풀이 기록 (0) | 2022.09.10 |
| 220908 문제 풀이 기록 (0) | 2022.09.10 |
220910 문제 풀이 기록
G5 | 13910 - 개업
풀이 시간: 약 10분
시도 횟수: 5회
체감 난이도: G4
풀이 쓸 의향: 下
풀이
기본 냅색 DP
여담: div3 버추얼 돌리기 전에 빠르게 풀어봄.
*800 | 1714A. Everyone Loves to Sleep
풀이 시간: 3분
시도 횟수: 1회
체감 난이도: B1
풀이 쓸 의향: 下
풀이
시간을 분으로 바꿔서 나타내자
여담: 곧 있을 div3 대비? 코포 버추얼. 어차피 div3은 unrated긴 한데 재미로 해봄.
*800 | 1714B. Remove Prefix
풀이 시간: 3분
시도 횟수: 1회
체감 난이도: B1
풀이 쓸 의향: 下
풀이
맨 뒤에서부터 하나씩 값 추가하면서 distinct 하지 않은 index 출력하기
여담: A보다 쉬운 B
*800 | 1714C. Minimum Varied Number
풀이 시간: 5분
시도 횟수: 1회
체감 난이도: S4?
풀이 쓸 의향: 下
풀이
앞부분 오름차순, 뒷부분 오름차순을 잘 엮으면 됨.
여담: 사실... 그냥 손으로 다 쓴 다음에 정답 45개 복붙해서 배열에 박았음. 코드 구현보다 이게 더 빠를것 같아서..
*1600 | 1714D. Color With Occurences
풀이 시간: 22분
시도 횟수: 1회
체감 난이도: G4?
풀이 쓸 의향: 下
풀이
텍스트 t에 대해 앞에서부터 차례대로, 최대한 오른쪽까지 커버 가능한 string 골라서 넣기. 하다가 안되면 -1
여담: 난이도가 무슨 ABC<<<E<D 느낌이었음... div3 난이도 맞추기가 상당히 어려워 보이긴 하는데...
*1400 | 1714E. Add Modulo 10
풀이 시간: 18분(-3분)
시도 횟수: 1회
체감 난이도: G5?
풀이 쓸 의향: 下
풀이
mod 10이 0일때, 5일때, 그 외 나눠서 보면 0이나 5면 무조건 각각 0번, 1번 더하면 더이상 바뀌지 않고, 나머지는 모두 2,4,6,8 돌아가며 나온다. mod 10이 2일때로 모두 고정한 뒤 (x/10)%2값이 하나라도 다르면 NO, 다 같으면 YES
여담: 풀면서 재밌었던 문제. 안타깝게도 이거 풀고나서 힘이 쭉 빠져서 E는 못풀었다... ;(
'PS > 풀이 기록장' 카테고리의 다른 글
| 220912 문제 풀이 기록 (0) | 2022.09.13 |
|---|---|
| 220911 문제 풀이 기록 (0) | 2022.09.11 |
| 220909 문제 풀이 기록 (0) | 2022.09.10 |
| 220908 문제 풀이 기록 (0) | 2022.09.10 |
| 220907 문제 풀이 기록 (0) | 2022.09.08 |
220909 문제 풀이 기록
P3 | 16909 - 카드 구매하기 3
풀이 시간: 1시간 + a
시도 횟수: 1회
체감 난이도: P3
풀이 쓸 의향: 下
풀이
빼지는 값은 top이 작은 수가, 더해지는 값은 top이 큰 수가 오도록 해서 monotone stack을 두번 사용하여 합하기.
여담: 졸린 나머지 코드를 너무 난잡하게 짰다...
'PS > 풀이 기록장' 카테고리의 다른 글
| 220911 문제 풀이 기록 (0) | 2022.09.11 |
|---|---|
| 220910 문제 풀이 기록 (0) | 2022.09.11 |
| 220908 문제 풀이 기록 (0) | 2022.09.10 |
| 220907 문제 풀이 기록 (0) | 2022.09.08 |
| 220906 문제 풀이 기록 (0) | 2022.09.06 |