leo020630의 블로그

BOJ 12736 - Fireworks

오늘은 원래 문제를 좀 더 풀려다가 교내 대회 등의 이슈로 바빠서 한 문제만 풀기로 마음먹었다. 이왕 푸는거 좀 좋은 문제를 풀어야 할 것 같았기 때문에 클10이면서 북마크에 정말 오래 있던 문제를 잡게 되었다. 유명한 문제이고 솔브 수도 많은데 시중에 적당한 자료가 없는 것 같아 풀이를 작성하려 한다. 문제 요약 가중치 있는 무향 트리가 주어지며, 간선 하나를 골라 가중치를 1만큼 변화시키는 연산을 할 수 있다. 1번 정점에서 모든 리프 정점까지의 거리를 모두 같게 하기 위해 필요한 연산의 최소 횟수를 구하여라. 풀이 (생각의 흐름) BOJ에서 풀었기 때문에 섭태는 잘 몰라 만점 풀이 기준으로 설명하겠다. \(dp(v,x)\) = \(v\)번 정점을 루트로 하는 서브트리에서 리프 정점..

오늘의 PS (29) - 240423~24

23일에는 지난 글에 IBory님이 남겨 주신 숙제 2개를 풀었고 24일에는 북마크에서 1개, 밀린 숙제에서 1개를 골라 풀었다. 30789 초콜릿 케이크 월향 본 대회에서 레이지 세그 쓴 이상한 풀이로 비비다가 패배했던 기억이 있는 문제이다. 저런 식으로 푸는 게 아니라는 정보 정도만 가지고 다시 풀어보기로 했다. 생각의 흐름 어떤 문제든 간에 엄청난 직관의 소유자가 아닌 이상 식을 좀 써 봐야 실마리가 잡히는 것 같다. \(D_i\) = \(i\)번 조각을 시작으로 피자를 잘랐을 때 두 부분의 맛의 차이(절댓값)으로 정의하자. 이를 가지고 뭔가 해보려 했으나 잘 되지 않았고, 절댓값을 뗀 후 각 조각에 초콜릿을 놓았을 때 \(D\)값의 변화량을 관찰하였다. 그러면 아래와 같은 두..

심심해서 문제를 조금 풀었다. 19852 공정한 회의 얼마 전에 petamingks가 던져 주었던 문제인데, 그 때는 진지하게 생각하지 않았다가 오늘 수업 시간에 갑자기 생각나 다시 잡았다. 생각의 흐름 triangle을 보았을 때 각 간선의 가중치가 모두 같거나, a a b (a < b) 형태여야 한다. 가장 처음 한 것은 불가능함과 동치인 깔끔한 조건을 찾는 것이었다. 정말 많은 시도를 했으나 모두 실패했다. 그래서 그냥 풀이를 먼저 찾아보기로 했다. 전에 했던 관찰 중 하나는 MST 느낌으로 간선을 가중치 순서대로 훑으면서 잘 합치는 것이었다. 당시에는 작은 것부터 보아서 반례가 존재했는데, 생각해보니 큰 간선부터 보면 잘 될 것 같았다. 그 이유는 triangle이 a b b 형태일 수 없어서 가..

시험도 끝났겠다 앳코더 계정을 옐로로 올려놓기 위해 ABC를 쳤다. A. Zero Sum Game (0:01, +) * 제목에 풀이가 써 있다. Zero Sum Game이므로 -(주어지는 수의 합)을 출력하자. B. Commencement (0:03, +) * 시키는 대로 구현해주면 된다. C. Airport Code (0:09, +2) * 앞에서부터 \(T\)의 각 문자가 등장할 때마다 그리디하게 골라주면 된다. 코딩을 절어서 2번 틀렸다. D. Divide Interval (0:15, +) * 정확한 증명은 모르겠지만 왠지 그래야 할 것 같은 코드를 짜서 맞았다. 갈 수 있는 한 최대로 계속 가주면 된다. E. Weighted Tic-Tac-Toe (0:27, +1) * 일단 게임이고, 제한을 보면 ..

팀원들과의 수 차례 논의 끝에 월파에서 메달을 따기로 했다. (의역 다수) 아직은 팀 내에서 자주 나오는 헛소리에 가깝지만, 메달까지는 아니더라도 이왕 힘들게 딴 티켓이 아쉽지 않도록 남은 기간 동안 공부를 열심히 할 것 같다. 나는 올해 리저널 (그리고 아마 Asia Pacific Championship도) 을 한 번 더 쳐야 하기도 하고.. 내가 생각하기에 우리 팀.. 인지는 모르겠고 나의 문제는 한 문제에 대해 깊게 생각하지 못한다는 점이다. 아마도 PS 연습을 CP 위주로만 해서 그런 것 같은데, 이 부분에서 OI를 진지하게 판 사람들과의 차이가 벌어진다고 생각했다. 다이아 이상 문제에서 얻었어야 하는 능력이나 사고 과정이 부족한 느낌을 받을 때가 있다. 물론 주위에 OI를 열심히 한 사람이 없어..

여러 이슈로 1달만에 치는 코포다. A. Did We Get Everything Covered? (0:09, +) 딥1 A인만큼 막 쉽지는 않았다. 하지만 뭔가 어떻게 해야 한다는 직감이 빠르게 들어서 그대로 짰다. 각 문자가 1개씩 등장할 때까지 뽑는 것을 반복하면 된다. 역추적을 대충 생각했다가 예제가 나오지 않아 고쳐서 맞았다. 역추적은 각 차례에서 가장 늦게 등장한 알파벳을 저장해주면 된다. B. Space Harbour (0:34, +) B번에서는 코포답지 않게 국밥 냄새가 강하게 났다. 최대한 빨리 풀어야한다는 마음가짐으로 문제를 읽었다. 읽어보니 업데이트는 대충 셋에서 양쪽을 보면 되고, 구간을 일차함수로 초기화하는 레이지 세그가 있으면 될 것 같았다. 조금 생각해보니 잘 짜면 될 것 같아서..

써야지 써야지 하다가 밀려서 그냥 1주일동안 한 것을 정리한다. USACO 2023 December Contest (12/26~29) Bronze 1. Candy Cane Feast *G3 쭉 순회하며 사탕을 먹이는 정상적인 \(O(N)\) 과정을 거치면 가장 앞 사탕은 적어도 길이가 2배가 됨을 알 수 있다. 따라서 이러한 과정은 최대 \(logX\)번 일어나고, 그 이상부터는 반드시 첫 사탕 선에서 막힌다. 2. Cowntact Tracing 2 *G3 우선 시키는 대로 1 덩어리들로 묶어준 후, 가장 작은 덩어리에 맞춰주자. 이 때 양 쪽 끝에 붙은 덩어리에 유의해야 한다. 3. Farmer John Actually Farms *G2 순서를 strict하게 잘 정해주어야 하므로 정렬된 결과에서 인접..

학기가 끝났다. 2학기는 ICPC 말고는 별로 기억에 남는 게 없어서 따로 후기를 쓰지는 않을 것 같다. (레이트로 냈지만) 마지막 과제 듀가 24일이여서 오늘부터 본격적으로 PS 재활에 들어갔다. 12월 25일이 무슨 날이라고 하던데 잘 모르겠다. 먼저 최근에 안친 오픈컨 문제들 중 재밌어 보이는 몇 개를 골라 풀었다. 31003 - 언젠가 정렬이 될 수 있으면 좋겠네. (2023년 12월 월향 E) *G1 DAG 만들고 위상정렬 갈겼다. 정해는 아닌 것 같다. 31006 - 역삼각형 (2023년 12월 월향 J) *P3 세그 스위핑 갈겼다. 6개 만들어서 좀 귀찮았지만 펜윅이라 다행이었다. 30998 - 최고의 크리스마스트리 (2023 미적확통컵 PE) *P3 리루팅 DP 갈겼다. 식 정리가 좀 귀찮..

결과가 나오고 쓰겠습니다. 점수가 애매해서 손발이 벌벌 떨리네요..

블로그에 처음 쓰는 아레나 후기 글이다. 아레나 #1은 계절학교와 병행해서 + C를 그냥 못 풀어서 등수를 박았고, 아레나 #2는 할 만큼 했으나 페널티로 인해 낮은 퍼포를 받았다. 두 대회 모두 딱히 복기할 거리도 없었다. 아레나 #3인 MatKor Cup은 깡수학 대회라길래 걸렀고, 아레나 #4 KSA 대회는 검수진이었다. 이러한 상황에서 아레나 #5인 SUAPC는 잘 칠 필요가 있었기 때문에 조금 집중해서 대회를 쳤다. SUAPC는 지난 2번의 대회에 출제진으로 참여한 적도 있었던 만큼, 기대를 안고 대회를 쳤다. ~0:12 대회를 켰는데, 일단 문제 수가 많았다. 내가 알기로 SUAPC는 13문제 체제로 유지되었던 것 같은데, 14문제가 나를 반기고 있었다. 같은 상황을 겪은 PPC와 대충 비슷한..