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..

문제를 풀었다. 요약 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를 열심히 한 사람이 없어..

여러 이슈로 1달만에 치는 코포다. A. Did We Get Everything Covered? (0:09, +) 딥1 A인만큼 막 쉽지는 않았다. 하지만 뭔가 어떻게 해야 한다는 직감이 빠르게 들어서 그대로 짰다. 각 문자가 1개씩 등장할 때까지 뽑는 것을 반복하면 된다. 역추적을 대충 생각했다가 예제가 나오지 않아 고쳐서 맞았다. 역추적은 각 차례에서 가장 늦게 등장한 알파벳을 저장해주면 된다. B. Space Harbour (0:34, +) B번에서는 코포답지 않게 국밥 냄새가 강하게 났다. 최대한 빨리 풀어야한다는 마음가짐으로 문제를 읽었다. 읽어보니 업데이트는 대충 셋에서 양쪽을 보면 되고, 구간을 일차함수로 초기화하는 레이지 세그가 있으면 될 것 같았다. 조금 생각해보니 잘 짜면 될 것 같아서..