2024. 5. 27. 12:12ㆍPS/Problem Solving
https://master.d66dlzauezpcp.amplifyapp.com/pentagon03
1~3일차 푼 문제 정리를 해볼까 한다. 티어는 푼 시점 기준이다. 볼드체 해놓은 문제는 어려웠던거나 추하는것.
1일차
골5
46분
대망의 첫 문제고 골드가 나와서 당황했다.
dp로 잘 비빌 수 있을거 같지만 n이 작아서 비트마스크로 모든 가능한 경우를 다 해보는 쪽으로 방향을 선회했다.
Off-by-One error의 심각성을 확연히 알 수 있었던 문제.
구현하면서도 계속 헷갈려서 46분을 허비했다. 비트마스크만 나오면 요상한? 최적화를 해서 등수를 높이려는 욕심이 있는데 여기서 이걸 확실히 느꼈다.
---
골4
14분
다음 문제는 한글 문제 + 이해하기 쉬운 알고리즘 수업이 나와서 내심 안심했다.
좌표압축 후 시뮬레이션 돌리면 된다. 문제 잘만들었다.
머릿속으로는 푼 것에 비해 이것도 오래 걸렸다.
---
골5
24분
얼핏보면 맨해튼 거리에서 최단거리를 구하는 것 같지만 잘 읽어보면 y좌표가 고정이라 그냥 정렬 후 그리디하게 골라주면 된다. 투포인터가 되긴 할텐데 또 짜다가 말리기 싫어서 upper bound 사용했다.
근데 일반적인 경우에도 분명 가능했던 것 같아서 구글링 하다가,
최소 / 최대 맨해튼 거리 (Manhattan Distance)
찾았다.
유클리드 / 맨해튼 / 체비셰프 거리가 있는데, 이거 총집합이 백준에 문제로 있다.
유클리드: 직각삼각형의 빗변
맨해튼: x 좌표 차 + y 좌표 차
체비셰프: max(x 좌표 차, y 좌표 차)
맨해튼 좌표계와 체비셰프 좌표계는 서로 변환 가능하다. 기본적으로 45도 돌린건데, 맨해튼 좌표계를, 대각선에 대한 좌표로 나타내는거다. (x,y) => (x+y, x-y)로 바꾸면 된다. KOI 조명등에도 이 트릭이 사용된다.
아직 안 풀어서 코드는 https://justicehui.github.io/ps/2021/08/31/BOJ1830/ 참고하시고..
유클리드 최대거리: Rotating calipus
유클리드 최소거리: 분할정복(현재까지 구한 ans 기준 최대 9개 점 보기) or 스위핑 (set 이용)
맨해튼 최대거리: 절댓값을 풀어주면 (x1+y1) - (x2+y2) OR (x1-y1) - (x2-y2) 꼴이 되어서 각각 정렬한 후 최대 차이를 구해주면 된다. 증명은 https://cs.stackexchange.com/questions/106289/can-someone-explain-this-formula-for-calculating-manhattan-distance 참고. 체비셰프로 바꿔서 최대 거리를 구해주는 것과 동일하다.
맨해튼 최소거리: 유클리드 최소 거리와 비슷하게 분할정복으로 할 수 있다고 한다. https://www.baeldung.com/cs/minimal-manhattan-distance
체비셰프 최대거리: max(x좌표 최대-최소, y좌표 최대-최소)
체비셰프 최소거리: 맨해튼 최소거리와 동일하게 분할정복으로 할 수 있다.
랜디는 처음 해보는데, 다양한 문제를 만난 후 복습이 되어서 되게 좋다.
---
골5
49분 40초
오랜만에 보는 풀기 싫게 생긴 문제다.
이런 표 나온 것부터 너무 싫어서 그냥 GPT한테 맡기고 쉴려 했더니
해석도 웬지 이상하고, 준 파이썬 코드 고치다가 시간 다 갔다.
그냥 지금은 나를 믿고 그냥 읽자.. 다시 읽어보니 티어답게 문제 자체는 쉬웠다.
모든 문자열 t에 대해서 이 t가 True 또는 False일 때 얻을 수 있는 페널티를 계산한다음 Min Max를 구해주면 된다.
오랜만에 토플이라도 다시 공부하면 PS 독해력이 향상될까 잠깐 고민했다.
---
골3
64분 30초
직전 것보다 훨씬 더 풀기 싫은 문제가 나올지 전혀 예상하지 못했다.
코드잼 스타일이랑 너무 안 맞는듯..
분명히 골3이라는데 문제 이해도 어렵고, 무슨 예제 테케는 Easy 버전이랑 무관한 Hard 버전으로 줘서 문제 이해에만 30분 이상 썼다. 처음에 어? 조건이 왜 이러지? 했던게 사실 이 문제를 Easy하게 만드는 요인이였는데, 난 내가 문제를 잘못 읽은 줄 알고 계속 고민했다. 그냥 내가 첨부터 끝까지 문제 읽는게 제일 낫다.
https://www.acmicpc.net/problem/10158
이 문제랑 비슷하게 무한히 반사시키는 것으로 생각할 수 있고,
d가 작으므로 dx^2 + dy^2 < d^2인 모든 dx, dy 쌍을 보면서 실제로 제자리에 돌아오는지 체크해주면 된다.
dx, dy가 서로소가 아닐 수도 있으므로 dx, dy를 서로소로 만들어서 속도 벡터의 개수를 세주면 답을 구할 수 있다.
이게 실수는 안되나 잠깐(오래) 고민했는데 다시 보면, 움직인 '실제 거리'인 dx, dy를 구해주면 그런 고민을 안해도 된다.
몇 번 틀려서 멘붕오다가 30초 전에 간신히 맞았다.
---
실1
7분
드디어 실버가 나왔다;;
C++로 하려면 이상한 소인수분해 해야할 것 같은 삘이 와서 그냥 파이썬으로 주어진 그대로 구현했다.
개인적으로 "특정 언어에서 쉬운"으로 난이도를 매기는 것은 모호한 여지가 너무 많다.
나중에 "PS"라는 언어가 나와서 atcoder 라이브러리를 지원하면, 2-sat같은 것도 실버가 될텐데, min(C++, Python)이라는 기여 기준이 제일 정확해보인다.
---
골2
PASSED, 65분.
65분 꽉꽉 채워서 고민했는데 결국 못 풀었다.
Per Austrin을 보자말자 Pass 했어야 되나 싶다.
이분은 매년 ICPC WF에 대한 비공식 출제자 에디토리얼을 작성하는 사람이다. 본게 많고 들은게 많은 사람. KTH의 조교수로 알고 있다.
보자말자 knasack 같아서 열심히 고민하고, 신뢰의 구현을 했는데 끝까지 예제도 안 나왔다..
Upsolved쉬운 문제라고 판단해서 문제 관찰을, "어떻게 dp를 정의할 것인가"에만 초점을 맞췄는데, 문제의 본질을 봤어야 한다.사실 p가 높은걸 먼저 하는게 이득이기 때문에 정렬해도 무방하고, 몇개 풀지 개수를 정하면 그리디하게 풀 문제를 선정할 수 있다. 이 관찰을 아예 놓쳐서 아쉬움이 적었다. 오늘도 배움
---
골5
10분
그냥 bfs. 구현하면서 생각해서 나름 빨리 짰다. 그래도 더 빨라져야 함.
---
골1
16분
골1 나와서 살짝 긴장했는데 다행히 쉬웠다. 문제 읽는데 살짝 어려움이 있었지만, 잘 이해해보면 결국 MST다.
---
골3
53분 30초
이왜골3?
digit dp는 볼 때마다 힘들다. 옛날 고등학교 때는 이런거 조합 NGD처럼 잘만 생각했는데 나이 먹더니 깔끔하게 풀고 싶어서 머리가 잘 안 돌아간다.
결국 1~N중에서, 어떤 string s를 subsequence로 가지는 수의 개수를 구하는 문제다.
s가 2023으로 고정되어 있어서, 포함과 배제로 잘 비비려 하다가 너무 복잡해서 포기했고
digit dp로 선회했다.
쉽게 푸려다가 잘 안 떠올라서 그냥 두개의 dp를 각각 나눠서 풀었다.
일단 주어진 N을 뒤집어서 1의 자릿수부터 생각한다.
// f(i, k): N의 i번째 자릿수까지 정확히 s의 인덱스 k까지만 사용할 수 있는 수의 개수
// g(i, j, k): 임의의 수의 i번째 자릿수를 숫자 j로 설정했을 때 정확히 s의 인덱스 k까지만 사용할 수 있는 수의 개수
이제 저 '정확히' k를 처리해주려고 꽤나 힘든 고민의 과정을 거쳤다.
너무 뇌절했는데 풀고 나서 짧은 코드 보니까 일단 N의 큰 자릿수부터 본다.
한가지 관찰을 할 수 있는데, 만약 지금 쓰는 수가 N의 1~i prefix와 수가 정확히 똑같은 경우
i+1번째는 무조건 작거나 같아야 한다는거다. 그래서 prefix에 대한 boolean 값을 설정해주면
i+1번째 자리에 어떤 수를 쓸지 알 수 있다.
dp(i, j, k): N의 i번째 인덱스까지 봤을 때, 현재 prefix와 모두 수가 같은지에 대한 여부가 j(true/false)이고, s(2023)의 k번째 인덱스까지 썼을 때 가능한 경우의 수
이렇게 두면 10줄짜리 재귀 dp로 풀이가 가능하다.
코드는 짧지만 안 풀어봤으면 절대 못 푸는 유형으로 보인다.
---
골3
49분
아니 어려운거 나온지 얼마나 됐다고 이상한 인터랙티브 나와서 정신 나갈뻔했다.
이 악물고 관찰해보면 항상 10만개 쓰고 0부터 99...8까지 3개 단위로 잘라서 첫번째것만 항상 다 써주면 33.33 개 제한을 넘지 않고, mod 3에 대한 1, 2는 알아서 잘 정해주면 된다. vector<bool>로 관리 가능.
풀기 전엔 지옥
아 그리고 이 문제 풀면서, 처음으로 인터랙티브는 문제는 커스톰 체커를 만들필요 없다는걸 깨달았다.
지금이야 깨달은게 엄처난데 그냥 터미널로 직접 입력하면 되는거였구나. 그동안 CPH로 해서 맨날 랜덤 돌리거나 직접 코드에 적었는데 지금에야 안게 레전드다. 인터랙티브가 앞으로 더 편해질듯
---
2일차
골1
34분
IOI문제가 나와서 신기했다. 이런 문제도 있구나. 또 머리 좋은 천재들의 난이도 투표 기만이겠걸리 생각했는데 나름 쉬웠다.
핵심은 A, T, C로 알파벳이 한정되어 있으므로
A A T T C C
T C A C A T
2개씩 뒤바뀐 쌍 먼저 처리해주고, 남은건 순환시켜서 처리해주면 된다.
이걸로도 바로 검사 가능할텐데, 그냥 누적합으로 처음에 개수 세줘서 가능/불가능 판별했다.
---
골1
19분
전형적인 exchange argument식 그리디인데, 망설임없이 수식 정리해보면 da - db가 작은 순으로 진행하는게 유리하다.
구현은 나름 어려운 편이다. 골1 받은 이유가 있다. 살짝 힌트를 남기면 da-db가 음수일 때, 양수일 때로 나눠서 처리할 수 있다.
---
골3
10분
이왜골3 하면서 열심히 스위핑 (1, -1 트릭) 구현했는데 좌표 범위가 작아서 단순한 누적합으로 돼서 슬펐다..
누적합 떠올렸으면 5분컷했을텐데 아쉽
---
플5
25분
푼 사람 1명 + 그 사람이 xiaowuc1 + 이상한 출력 조건 때문에
PASS 버튼 누를까 심각하게 고민했는데
첫 플5기도 하고 문제를 찬찬히 읽어보니
머릿속에 잘 그리면 원을 타고 가는 문제랑 동일해서 좌표 평면을 가로막는 연결된 원 집합이 없는지 판별해주면 된다.
이건 dfs/bfs로 가능하고 난 dfs로 했다.
출력 조건이 너무 모호해서 그냥 소수점 2자리로 찍었는데 맞았다.
글 남김.. https://www.acmicpc.net/board/view/143515
문제 자체는 되게 참신하고 좋다.
재밌는 문제집 많이 사랑해주세요.
---
플5
9분
gggkik님의 좋은 문제중 하나. 예전에 안전영역(More)을 풀었던게 기억에 남아서 보자말자 바로 생각나서 구현했다.
9분컷 굿..
본인 말로는 트리 위에서 히스토그램이라는데 생각해보니 그 말도 맞다.
다음은 풀 때 메모한 내용이다.
"트리에서 연결된 부분트리를 골라서
min(A) * |A|를 최대화 시키는 문제
이러한 문제의 경우 min(A)를 고정시켜서 푸는 경우가 많다.
sort + UF
min(A)를 큰 것부터 하면 최솟값도 바로 알 수 있다."
교육적이다.
--
골2
40분
이 문제도 쉽지 않았다. 보자말자 knapsack인건 알았는데 말을 너무 이상하게 써놔서 도대체 정확히 뭘 구하라는걸 알 수가 없었다. 한 5번 더 읽고서야 정확히 m, u를 써야되는걸 알았다.
무슨 문제인지는 기억 안나는데 사탕가게인가? 소수점 두 자리에 100을 곱해서 (int)로 변환하면 정확하지 않다!는 교훈이 너무 충격적이여서 이번에는 round 함수를 썼다. wider93님이랑 frozenca님이 열심히 설명해주셨던 기억이 난다. 그거 아니였으면 맞왜틀 당하다가 또 Pass할 뻔 했다.
--
플4
29분
문제 풀다가 해야할 일이 있어서 잠깐 하고 왔다. 실제로 푼 건 15분 남짓.
읽자말자 SCC 같아서 찍었더니 예제 맞길래 제출했다. AC.
잘 생각해보면 SCC가 잘 된다.
근데 잘 몰랐는데 outdegree = 0인 SCC의 개수는 결국 간선 뒤집은거에서 indegree = 0인 SCC의 개수와 같고, 이는 그냥 단순한 dfs로 가능하다. ?.. SCC 개념 없어도 그냥 관찰로 풀 수 있는 문제 같다. SCC 뇌절 안하고 푼 사람이 많아지면 골3까지 내려갈 거 같은 문제.
---
골1
17분
밖에 나갔다 오고 밤에 또 문제를 잡았다. 생긴건 bit dp처럼 생겼는데 잘 보면 항상 가로 방향만 가능해서 분할정복 거듭제곱 이용해서 쉽게 풀 수 있다.
---
플2
15분
운이 굉장히 좋았다. 이 문제는 minimum cyclic shift를 구하는 문제다.
지금 플2로 기여된게 Suffix Array의 응용으로 알려져 있어 플2로 되어 있는데, 내 suffix array 구현체는 https://cp-algorithms.com/string/suffix-array.html 여기서 들고 온거라 그냥 suffix array와 사실 동일한 문제가 된다.
문제는 카운팅 정렬은 stable sort가 아니여서 같은 문자열의 경우 인덱스가 마구잡이로 섞인다. https://howtoliveworldnice.tistory.com/319 옛날에 적어놓은 글이 문득 생각나서 구현을 잘 봤더니 저거랑 똑같았다;; 아마 counting sort 이슈가 아니라 다른데 있는거 같은데 저걸 다시 공부할 여유는 없어서 그냥 SA에서 binary lifting해서 범위 구하고, 그 범위에서 최소 인덱스는 선형으로 구했다. (어차피 O(n)).
SA로 할 경우 string을 2배해주고, LCP 배열을 통해서 그 범위를 선형에 찾을 수 있다.
---
플5
33분
재밌는 문제였다. 문제를 잘 읽어보면 어떤 정점에 대해,
서브트리 안/밖에 있는 정점 중 거리가 홀수 / 짝수인 정점의 개수
이 4가지를 효과적으로 구해야 한다.
난 dp 배열을 안 / 밖으로 나눠서 두 번 구했는데, gggkik님 코드를 보니 루트의 dp를 이용해서 기우성 차이?로 서브트리 안 정보만을 이용해서 밖을 구할 수 있나보다. 능지 이슈
---
3일차
플5
25분
wapas님 문제다. 지문에서 K가 왜 주어지는지 몰랐는데 알고보니 대회에서 나온 시리즈 문제여서 이 문제는, 전단계 문제의 스페셜 저지를 구현하는 문제였다. 이런거 너무 좋다. 문제의 핵심은 기존 트리의 조상관계가 전부 새로운 트리 안에 포함되어 있는지 확인하는 것이다. 이는 놀랍게도 루트에서부터 dfs하면서 새로운 트리의 조상 중 '자신의 부모'가 있는지만 확인하면 재귀적으로 전부 확인된다. LCA 풀이는 뭔지 모르겠다.
---
여담:
처음으로 제육볶음 했는데 굉장히 맛있었다.
쉬다가 코포를 봤고 재밌게 잘 봤다! 코포 당일에는 하루종일 쉬는게 좋네..
불 다 키고 릴보이 킬링버스 무한 반복하는게 좋았다.
음악 들으니까 A,B는 조금 집중 안됐는데 C,D부터는 굉장히 좋았다.
음악은 후반부터 듣자. D 안 풀려서 세수하고 오니까 풀렸다.
앞으로도 분위기 환기를 위해 노력해보자.
끝.
'PS > Problem Solving' 카테고리의 다른 글
| 랜덤디펜스 4일차 (0) | 2024.05.29 |
|---|---|
| [BOJ 17371] 이사 | 증명 (0) | 2023.01.07 |
| [BOJ 26035] “컷” $0101$ (1) | 2022.11.18 |
| [BOJ 25972] 도미노 무너트리기 "컷" (2) | 2022.11.17 |
| [BOJ 3679] 단순 다각형 "컷" (0) | 2022.11.17 |