leo020630의 블로그

백준 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 형태일 수 없어서 가..

시험도 끝났겠다 앳코더 계정을 옐로로 올려놓기 위해 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를 열심히 한 사람이 없어..