leo020630의 블로그

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

심심해서 문제를 조금 풀었다. 19852 공정한 회의 얼마 전에 petamingks가 던져 주었던 문제인데, 그 때는 진지하게 생각하지 않았다가 오늘 수업 시간에 갑자기 생각나 다시 잡았다. 생각의 흐름 triangle을 보았을 때 각 간선의 가중치가 모두 같거나, a a b (a < b) 형태여야 한다. 가장 처음 한 것은 불가능함과 동치인 깔끔한 조건을 찾는 것이었다. 정말 많은 시도를 했으나 모두 실패했다. 그래서 그냥 풀이를 먼저 찾아보기로 했다. 전에 했던 관찰 중 하나는 MST 느낌으로 간선을 가중치 순서대로 훑으면서 잘 합치는 것이었다. 당시에는 작은 것부터 보아서 반례가 존재했는데, 생각해보니 큰 간선부터 보면 잘 될 것 같았다. 그 이유는 triangle이 a b 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년 만에 오늘의 PS를 부활시켰다. 다음 글이 언제가 될진 잘 모르겠다.. 셋: https://www.acmicpc.net/category/detail/3626 A. 10! (0:01, +) *B4 구현해주면 된다. 0분대 솔브도 가능했을 것 같은데 똑똑한 방법을 찾지 못하고 계산기로 10!/6을 계산하느라 조금 늦었다. B. 고양이 카페 (0:06, +1) *S3 비슷한 문제를 굉장히 많이 봐서 바로 짰다. 제일 작은 원소부터 가능한 원소와 매칭시켜 주면 된다. upper를 lower로 잘못 써서 ..

하루에 대회 3개를 쳤기 때문에 묶어서 정리하려고 한다. BOJ - 초콜릿컵 A. 초콜릿 피라미드 (0:12, +) 차분히 식정리를 해주면 된다. B. 초콜릿과 나이트 게임 (0:32, +) $XY=0$인 경우, $X=Y$인 경우, 그 외의 경우로 나뉜다. 앞 두 케이스는 7번, 뒤 케이스는 15번만에 게임을 끝낼 수 있다. 구현이 좀 귀찮은데, 난 그냥 cout을 29개 썼다. C. 예쁜 초콜릿과 숫자놀이 (1:51, +3) 제한이 애매하게 커서 완탐도 안될 것 같고(사실 된다), $O(N^2 MOD)$ DP는 생각이 나지 않아 그냥 $O(N^3 MOD)$ DP에 비트셋을 박았다. 왠지는 모르겠지만 실행시간 1등이다. 비트셋 최고 D. 초콜릿 나눠 팔기 (2:09, +) 케이스를 나누면 ..

지난 포스트에서 글을 자주 쓰겠다고 했는데, 바쁘다고 미루다 보니 또 2주동안 글을 쓰지 않았다. 그동안 있던 SCPC 본선과 SUAPC는 별도의 글을 올릴 예정이다. 2주동안 있었던 코포랑 앳코더는 다 언레라 진지하게 치지 않아서 여기 올리기엔 좀 그런 것 같아 백준에서 푼 문제들만 정리해보려 한다. 2021 홍익대학교 프로그래밍 경진대회 23320 홍익 절대평가 그냥 구현. 문제가 친절해서 실수도 필요 없고 정렬도 필요 없다. 23321 홍익 댄스파티 그냥 구현. 귀엽긴 한데 무슨 말인지 알아보기가 좀 힘들었다. 23322 초콜릿 뺏어 먹기 코포식 그리디 문제이다. 풀이는 자명하게 찾을 수 있다. 23323 황소 다마고치 역시 코포식 그리디 문제이다. 어느 경우가 최적인지는 잘 생각해보면 알 수 있고..

블로그를 너무 방치해 둔 것 같아 오늘의 PS 글을 하루에 하나는 아니더라도, 일주일에 하나 정도는 써보려고 한다. UCPC가 끝난 이후부터는 개인 PS 공부를 정말 거의 하지 않아서 쓸 내용이 없었지만, 그래도 이번주부터는 뭐라도 해보려고 한다. SCPC 대비도 해야 하고.. 이번주에는 백준에서 셋 2개정도를 풀고, 코포 1번과 앳코더 2번을 쳤다. 코포는 2번이 더 있었으나 노느라 치지 못했고, 앳코더는 두 번 모두 쳤다. BOJ 화요일에는 동아리 연습용 셋으로 던져 놓은 2021 IUPC 를 풀었다. 마지막 문제 빼고는 모두 화요일에 풀었고, 마지막 문제는 귀찮아서 미루다가 오늘 풀었다. 23080 스키테일 암호 브론즈 문제이다. 잘 구현해주면 된다. 23081 오델로 실버 구현 문제인데, 제한이 ..

ARC랑 코포 Div.1을 쳤다. ARC 144 A. Digit Sum of 2x (0:04, +) *105 우선 111..11 식으로 배치하면 첫번째 답은 $2N$임을 자명하게 알 수 있다. 이러한 $x$는 각 자리수가 4 이하여야 하므로, 4를 최대한 많이 쓰는 식으로 나열해주면 된다. B. Gift Tax (0:19, +) *895 이분 탐색을 이용할 수 있다. \(a

13:00~15:30 모비스 본선 16:30~18:30? 천코대 오픈콘 23:35~01:35 에듀코포 를 쳤다. 모비스 대회에 대한 후기는 생략하도록 하겠다. 제6회 천하제일 코딩대회 본선 Open Contest 2시간 늦게 참여하기도 했고 중간에 자리를 몇 번 비워서 진지한 마음으로 치지는 않았다. 아마 종료때까지라도 했으면 F는 풀었을 것 같다. A. Gravity Hackenbush 지문 낚시 문제이다. 각 플레이어가 초록색 간선을 최대한 많이 쓰는 것이 최적이므로 이를 토대로 비교해주면 된다. C. Merge the Tree and Sequence Split the SSHS 문제와 세팅이 비슷하다. 간선을 묶는 것은 그때와 같이 하면 되고, 남은 부분은 간선을 묶는 것에 비하면 크게 어렵지 않다...