leo020630의 블로그

문제를 풀었다. 요약 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를 어떤 알파벳으로 바꿔서 준다. 이를 잘 해석해 각 숫자에 해당하는 알파벳을 맞추면 된다. 이런 문제의 경우 보통 통계적으로 좋아 보이는 방법 몇 가지를 찍어 보면 된다. 우선 ..

P4부터 시작했다. 18138. 리유나는 세일러복을 좋아해 (P4, 17:58) 이분 매칭 기본 문제이다. 코드를 안 보고 짠 데다가, 짧은 DFS 코드가 기억이 나지 않아 에드먼드 카프를 짜서 시간이 좀 걸렸다. 20560. 맛집 탐방 (P3, TLE) 갓문제들의 산실인 나코더 송년 대회 문제이다. 비슷한 문제(정확히는 이 문제의 하위호환)를 얼마 전에 풀었어서 첫 번째 조건은 어렵지 않게 구할 수 있었다. SCC로 만든 DAG에서 위상 정렬의 결과가 유일하면 된다. 문제는 두 번째였는데, 대충 생각했을 때 첫 번째 조건에 더해 DAG의 모양이 체인이면 된다는 사실을 알 수 있었다. 그리고 그대로 구현했더니 무수한 WA의 늪에 빠지고 말았다. 구현량이 좀 있어서 시간이 부족하기도 했고, 원래 한 번 말..

PS를 어떻게 할까 생각하다 어디서 본 좋고 재밌는 방법이 떠올라서 도전해본다. 랜덤으로 문제를 뽑아서, \(30 + max(0, (x-G1)*5) \) 분 안에 문제를 푸는 데에 성공하면 티어를 하나 올리고, 풀지 못하면 내린다. 자세한 사항은 https://blog.naver.com/bnb2011/222621250928 를 참고하시면 된다. 손도 풀 겸 G5부터 시작했다. 2187. 점 고르기 (G5, 11:56) G5인데 풀이가 바로 떠오르지 않아 당황했다. 한 5분정도 문제를 천천히 살펴보니 직사각형의 크기가 주어진다는 것을 알 수 있었다. 왼쪽 변의 좌표를 고정하고, 해당 x좌표에 들어오는 점들을 모은 후 스위핑해주면 된다. 이건 약간 멍청한 풀이고, 똑똑한 다른 풀이도 꽤 있는 듯 하다. 21..