leo020630의 블로그

무려 3주만에 글을 쓴다. 지난 텀이 2달을 넘겼던 것을 생각하면 장족의 발전이다. 대신 쓸 내용도 없어졌기에 근황만 적당히 전하고 도망가려 한다. BOJ 솔브수 4K 달성 + 랭킹 1페이지에 입성했다. 그냥 어제쯤 보니까 3996문제길래 팀연습에서 푼 코드 내고, 내친김에 좀 더 풀어서 1페이지까지 찍었다. 사실 오늘 글을 쓴 계기이기도 하다. 이제는 백준에서 4000문제를 풀어도 100명 안에 못 든다. 무서운 세상이다. 어차피 금방 내려갈 거라 별 생각은 없고.. 그냥 업적작 하나 끝낸 느낌이다. Codeforces 지난 글 이후로 2번의 라운드를 쳐서 3점이 올랐다. 앞의 라운드에서는 솔직히 셋이 좀 똥이었던 것을 감안해도 무관행동을 너무 해서 점수를 크게 깎아먹었고, 뒤 라운드는 적당히 쳤는..

???: 5.5월에 다시 올게요 조금 늦었다. 역시 2달 반 동안 많은 일이 있었기에 간단히만 정리해보겠다. Onsite Contest 4월~5월 초에 대부분의 개인 대회가 몰려 있었기에 이 포스팅 이후 다녀온 온사이트 개인 대회는 딱 하나이다. 코드트리에서 주최한 ACPC가 바로 그것이다. 예선때도 여러 말이 많았고, 상도 3등까지밖에 안 줘서 별 기대를 하고 가진 않았다. 본선 역시 처음부터 프린트와 웹사이트의 문제가 서로 다르다거나 없어야 할 문제가 끼어들어갔다거나 하는 이슈가 있었다. 대강 난이도 순인 것 같아서 앞부터 읽었고 3솔까지의 스퍼트가 30분 정도로 나쁘지 않았다. 이후 4번은 아호코라식 쓰는 문자열 문제 같았고, 5번이 트리라서 먼저 봤는데 풀이가 바로 나왔다. 다행히 한 번에 ..

최근 유독 정신이 없었다. 휴학하면 안 바쁠 줄 알고 일을 잔뜩 벌여놨더니 오히려 학교에 있을 때보다 더 힘든 것 같다. (사실 학교 다니면서 공부를 제대로 했던 적이 없긴 하다) 블로그도 자주 쓰기는 힘들 것 같아서 월마다 결산이라도 써야겠다는 생각을 5월 1일에 했는데, 눈떠보니 어느새 이 날짜가 되어 있었다. 마침 마지막으로 쓴 글이 1달쯤 지났길래 그냥 1달 결산을 월 중간쯤에 해 보려 한다. 글을 반쯤 썼는데 이미지가 하나도 없어서 급조해 넣었다. 조금 짜쳐도 봐주세요 BOJ에서 푼 것 중 재밌었던 문제24973 - Up Down Subsequence (Platinum I, 4/5)간단해 보이는데 꽤 많은 철학이 숨어 있었다. 31349 - Inverse KMP (Platinum II, 3..

코포 후기를 쉰지 좀 되었는데, 억울하고 부끄러운 마음에 더 정진하고자 이제부터라도 후기를 적으려 합니다.  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..

문제를 풀었다. 요약 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 형태일 수 없어서 가..