leo020630의 블로그

코포 후기를 쉰지 좀 되었는데, 억울하고 부끄러운 마음에 더 정진하고자 이제부터라도 후기를 적으려 합니다.  A. Diverse Game (0:02, +)배열을 밀면 된다. \(N=1\)이나 \(M=1\)인 경우만 유의해주자. B. Fun Game (0:10, +)s를 조작했을 때, 가장 처음에 등장하는 1 뒤로는 자유롭게 바꾸어줄 수 있다. 따라서 두 문자열에서 가장 먼저 등장하는 1의 위치를 구한 뒤 비교해주자. 역시 0으로만 이루어진 경우 등에 유의하자. C. Hungry Games (0:16, +)조건을 만족하지 않는 구간의 수를 구해 보자. 이분 탐색 또는 투 포인터를 이용해 각 시작 위치에 대해 \(X\)를 처음 넘기는 지점을 구한 후, 이를 적절히 합치면 된다. D. Funny Game (0..

서론올해 역시 UCPC에 출전하였다. 작년에는 모종의 이유로 팀이 조금 달랐어서 1557 팀으로는 처음 (그리고 아마도 마지막) 으로 나가는 UCPC이다. 팀명은 이 글에서 밝혔듯 WF를 향한 우리 팀의 포부를 담아 지었다. 뱉은 말에 대한 책임을 지지 않아도 되는 것이 언더독의 특권이 아닐까? 포스텍에서는 4팀이 예선에 참가하였다. 4학년이 되어서야 UCPC 본선 진출이 상당히 힘들다는 것을 깨닫고 의도적으로 홍보를 좀 덜 했다. 대신 각 팀의 개별 전력은 조금 세진 느낌이라 본선 진출에 대한 가능성은 더 높아졌다고 생각했다. 대회 전UCPC 예선 당일을 포함한 주말에는 POSCAT 부원들과 함께하는 일본 여행이 있었다. 아쉬운 점은 여행 계획과 항공권, 숙소 등 각종 예약을 모두 끝낸 후에야 UCPC..

백준 3000솔을 찍었다. 3000번째 문제로 의미있고 어려운 문제를 풀고 싶은 생각도 있었는데 마라톤 다 밀면 딱 3000이길래 포기하고 그냥 풀었다.   인터넷에 현대모비스 대회 후기가 많이 없는지 대회 공지가 뜬 시점부터 조회수가 확 튀었다. 대회를 썩 잘 치지 못했어서 아무 말이나 해 놓은 푸념에 가까운지라 조금 부끄러웠다. 나도 모비스 나가고 싶다... 본선 진출하신 분들 모두 화이팅입니다. 이제 진짜 뻘글 그만 쓰고 팀 연습 후기로 찾아오겠습니다.많관부

거진 한달만에 글을 씁니다. 종강을 한 지도 3주가 다 되어 가는데, 다짐했던 것보다는 공부를 안 하고 있습니다. 그동안은 밀린 게임을 열심히 하고, 소멤 미팅 겸 본가도 다녀오는 등 알?찬 시간을 보냈습니다. 그 사이 드디어 월드 파이널 참가에 대한 공식적인 확인이 있었습니다. 다만 공식적이지만 공개적이지는 않아서 좀 불편한 감이 있습니다. 왜 이렇게 소통이 느린가요 Asia Pacific..   멀게만 느껴졌던 월파도 이제 100일이 채 남지 않았습니다. 팀 연습을 얼마 전에 재개했는데 계속 한 끗이 부족한 느낌입니다.팀 연습은 유니버셜 컵 (https://ucup.ac/) 에서 하고 있습니다. 문제가 너무 어려워서 풀이 죽을 때가 있다는 점을 제외하면 다 좋은 플랫폼 같습니다. 월파 진출 이상을 노..

문제를 풀었다. 요약 13810. Futon (Gold I, 10:30) PPC 기출인 이 문제와 비슷하다. 인접한 두 칸에 대해 만약 같은 Futon에 속한다면 다른 색 (머리-다리), 다른 Futon에 속한다면 같은 색 (머리-머리, 다리-다리) 로 칠해져야 한다. 이분 그래프 판별을 응용해 해결할 수 있다. 그래프가 조금 귀찮게 주어지는 점에 유의하자. 3037. 혼란 (Gold I, 8:10) \(DP[i][j]\) 를 길이가 \(i\), inversion이 \(j\)개인 수열의 개수로 정의하자. 이러면 \(DP[i][j] = DP[i-1][j] + \cdots + DP[i-1][j-i+1]\)로 구할 수 있다. (\(i\)를 끼워넣는 위치에 따라 inversion의 증가량이 결정된다.) 이를 그..

코포 이슈로 하루 쉬고 이어서 문제를 풀었다. 코포는 엄청 절었는데 다행히 점수는 많이 안 떨어졌다. 요약 11464. Hacking the Screen (Gold IV, 36:18)  1일차에 이어 PASSED가 하고 싶게 생긴 녀석이 첫 문제로 나왔다.그래도 티어답게 나름 친절한 구석이 있어서 그냥 짜기로 했다. 풀고 나서 보니 python의 eval인가 하는 함수로 편하게 하는 방법도 있다고 한다. 그게 뭔데..  15625. Paprike (Gold III, 4:18) 웰노운 트리 DP 유형이다. 합이 큰 자식부터 그리디하게 잘라 주는 과정을 반복하면 된다. 골3치고는 어려운 것 같아서 기여했더니 골2가 되었다. 2155. 삼각형의 최단 경로 (Gold IV, 13:10) 각 삼각형을 2차원 좌표..

레이팅만 달렸다면 환장하는 PS러들을 위한 좋은 확장 프로그램이 생겨 열심히 문제를 풀었다.자세한 것은 https://master.d66dlzauezpcp.amplifyapp.com/ 를 참고하자. 참 잘 만든 것 같다. 요약 27809. Overrandomized (Gold IV, 24:33) 첫 문제부터 GCJ 출신의 TL 20초, N = 10000 고정, 입력이 랜덤으로 생성되는 문제가 나왔다. 탈주할까도 고민했지만 골4에서 탈주하는 것도 좀 그래서 열심히 찍어보았다. 문제를 요약하자면 숫자가 10000개 주어지되, 0~9를 어떤 알파벳으로 바꿔서 준다. 이를 잘 해석해 각 숫자에 해당하는 알파벳을 맞추면 된다. 이런 문제의 경우 보통 통계적으로 좋아 보이는 방법 몇 가지를 찍어 보면 된다. 우선 ..

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

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

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