본문 바로가기

PS

 (13)
Kick Start 2020#A Bundling 대충 재활훈련 (재활할 실력이 있었나 싶지만 ㅋㅋ) 힘내서 풀어보자 아자아자 Round A의 다른 세 문제는 블로그 어딘가 풀이를 올렸었다. 당시에 시간 내에 못 풀었던 Bundling만 풀어보자. # Bundling [문제] N개의 문자열이 있고 K개의 그룹으로 나눴을 때 점수 합의 최댓값을 구하여라. 그룹의 점수는 문자열의 공통 Prefix의 길이이다. [풀이] 그 안에 원소가 몇 개가 있든 상관없이 공통 Prefix가 많아야한다가 핵심이다. 트라이 만들고 가장 긴 원소를 기준으로 Prefix가 긴 것부터 K개씩 뽑아오면 된다. [고찰] 대충 트라이 만들고 그리디하게 어찌저찌 하면 된다는 점은 눈치채기 쉽다. K개를 뽑아올 때, 가장 긴 거를 기준으로 K개를 뽑아오는게 이득일지, 아니면 가장 긴 K개..
BOJ#11932 트리와 K번째 수 PST 응용 문제 ~ 이 문제를 풀고 싶다면 #7469 K번째 수를 PST로 풀고 오자. 어차피 짜야하는 부분이 같다. 저 문제는 배열에서 K번째 수를 처리하는 것이고, 이 문제는 트리에서 처리해야한다. 그렇지만 선형 연산을 이용해서 풀 수 있다. 왜? root부터 다른 정점까지는 선형이며, 정답을 위한 쿼리는 (root부터 x) + (root부터 y) - (root부터 lca) - (root부터 parent[lca])로 돌릴 수 있다. parent[lca]를 빼는 이유는 lca는 한 번만 빼줘야하기 때문이다. 1 2 3 4 5 int query(int x, int y, int k) { int l = lca.query(x, y); int pl = lca.par[l][0]; if(l==1 && pl == ..
BOJ#1626 두 번째로 작은 스패닝 트리 다야 캐야지 ~ 다이야 문제들의 특징은 풀이가 너무 이해하기 어렵다는 점인데, 이 문제는 선수문제(그래프와 MST)가 비교적 쉬운데, 저걸 풀면 바로 이해가 가며, 좀만 더 고치면 맞을 수 있다. 까다로운 반례 좀 있고, 추가된 테스트케이스가 많은 문제이다. 인터넷에 돌아다니는 블로그 중, 오래된 블로그 같은 경우에는 재채점 이후 틀린 코드가 꽤 있으니 주의하자.(내 계정은 nemo이며, 이 글을 작성하는 시점에서는 맞았다.)이 글에서는 그래프와 MST를 풀었다는 가정 아래 풀이를 설명하고자 한다. 안 풀었다면 풀러 가자. 어차피 짜야하는 부분이 같다. 당연하겠지만 가장 먼저 하게 되는 생각은 그래프와 MST의 정답을 정렬한 후 두 번째로 큰 답을 출력하면 되는 거 아닌가이다. 근데 몇 가지 조금 더 고..
UCPC 2020 예선 후기 서버 터지고 나의 성공 시대 시작됏다 서버 터지고 나의 등수 달라져따나는 DEGH를 풀었다. 시작하자마자 ADGH가 굉장히 빠르게 풀려서, 순간 등수 6등을 했었다. 그거 캡쳐하며 좋아했는데 최종 등수가 9등이라니 믿기지 않는다. 플래 한가득 세트 너무 좋고 ~ 팀원들이 잘하니까 내가 한 문제 풀면, 두 문제가 더 풀려있다. 너무 편하고 버추얼 성취감(?)을 두 배 더 느낄 수 있어서 좋다. 그리고 셋이 능력치가 다양해서, 플래 난이도의 문제는 풀다 어려워서 버리면 셋 중 하나는 그걸 풀 수 있다는 것도 좋다. (J 못풀어서 패널티 열심히 쌓다가 팀원1에게 버리고, I는 보자마자 팀원2에게 버렸다 ㅋㅋ 물론 나도 팀원2가 버린 E를 받아왔다) --- 미래에 생각나면 풀이 써야지. 대충 적어두자면 E는 바..
BOJ#18865 이제 다시 시작이다 자력 플1 기분 좋고 ~ 사실 처음에 풀면서 골드인 줄 알았고, 실제로 아이디어 자체는 그렇게 어렵지 않다.세그트리이니만큼 플5이상 보정받고 (응용이니 3~4 이상), 손으로 해야하는 계산이 좀 귀찮긴 했다. 쨋든 기분조아져서 풀이 써야지 [풀이]x = 스피커부터 (ex, ey) 까지의 맨해튼 거리라고 하자.세 개의 세그를 준비해서 x에 대응되는 인덱스에 각각 $1,\space x,\space, x^{2}$에 대한 SUM 연산을 수행하게 하자. ex, ey부터 시작해서 훈련소를 덮는 삼각형의 한 변의 길이는 v-x가 된다.이제 구간을 4개로 나누어서 생각하자. 훈련소의 가로, 세로 중 짧은 것을 m 긴 것을 M이라 하자. 1) v-x ∈ [0, m] x ∈ [v-m, v]2) v-x ∈ (m, M] x ..
ICPC 2017 인터넷 예선 업솔빙 후기 첫 팀연습이다 ~ ! 한 명은 작년에 함께 했던 친구이며 ICPC에 매년 나오는 쌩구현 문제를 담당하고, 한 분은 올해 새로 영입했으며 수학(!!)을 매우 잘하신다. 올해 팀 구성 꽤 좋당!! 나는 음료수 서빙해야지 오예 셋이 합쳐서 총 6문제를 풀었으며, 마지막에 각자 EFG를 잡고 있었는데, 다들 학기 중에 코딩을 쉬던 상태라 삽질을 많이 해서, 더 잘할 수도 있었을 것 같다. 인터넷 예선이라 그런지 전형적인 문제가 많았다. EFGL도 플래이니만큼 굉장히 풀만했던 문제인 것 같으며, 팀연습 후 개인 업솔빙을 통해 FGL을 풀어보았다. 플래 중에서는 #D Grashoppper Route, #E Jerry and Tom, #G Map Labeling이 굉장히 좋은 문제라고 생각한다. 내가 푼 문제에 대해..
Google Code Jam 2020 Round 1A 후기 잠수탄다는 네모 어디 많이 바쁘긴 한데 학기 중 대회 즐기는 걸 생각하면서 겨울방학에 그렇게 공부햇는데 안 치는 게 말이 안된다. 결과도 꽤 만족스럽게 나와서 후기 써야지! 코딩할 줄 알고 (Pattern Matching) / 파스칼 삼각형 들어봤고 비트연산 할 줄 알면 (Pascal Walk) 두 문제를 풀 수 있다. 마지막 문제를 잡을 때는 시간이 조금 남았는데 지문 읽으면 끝날 거 같아서 과제하러 튀었다. 킥스타트랑 다르게 구코잼은 더 큰(?) 대회인만큼 비전형적인 문제가 많다. 그래도 1라운드까지는 알고리즘을 쓰는 문제는 잘 안 나온다. # Pattern Matching [문제] a*b*c, a*b*, 이런식으로 여러 개의 문자열이 원본 문자열의 일부를 *으로 치환한 채로 주어진다. 원본 문자열을..
Kick Start Round A 2020 후기 얍! 후기 써야지네 문제 다 전형적인 느낌이다.코딩할 줄 알고 (Allocation) / DP (Plates) / 파라메트릭 서치 (Workout) / 트라이 (Bundling) 를 다루어봤다면 쉽게 풀이를 떠올릴 수 있다. 그렇지만 트라이를 살면서 한 번 짜봐서 4번이 나한테는 까다로웠을 것 같다. 3번까지 빠르게 풀어서 올솔할 수도 있었을 것 같은데, 중간에 잠들어서 결국 3솔했다 # Allocation [문제]N개의 집이 있고, 각각의 가격은 다르다. B달러가 있으면, 집을 최대 몇 개 살 수 있을까? [풀이]쉬운 그리디이다. 가격 순으로 정렬하고, 싼 것부터 사면 된다.# Plates [문제]N개의 묶음이 있고, 각 묶음에는 K개의 접시가 있다. ( 접시의 Beauty가 NxK 행렬로 주어진다. ..

티스토리툴바