dlwocks31의 PS일기장

문제 - https://www.acmicpc.net/category/detail/2053 최종 스코어보드 - https://ucpc.acmicpc.net/contest/spotboard/449 I HATE PS★팀으로 UCPC예선에 참가해 38등으로 본선진출에 성공했다! 대충 우리 팀이 뭘 했는지 30분 간격으로 기억나는대로 적어보겠다. 0-30분: A 9분 AC - gyuni가 시작하면서 읽고 바로 풀어냈다. B 18분 AC - 내가 읽고 바로 풀었다. 밀면서 좌표가 어떻게 매핑되는지 헷갈려서 살짝 헤맸지만.. 종이에 정리를 잘 하고 풀자! 그 후 E, F, C번 정도를 읽어봤는데 잘 모르겠어서 넘겼다. 30-60분: gyuni가 나한데 D번이 풀만한거 같다며 넘겨줬고, 나는 다소 해메다가 [해석할려는..

https://codeforces.com/contest/1197/standings/participant/26546079#p26546079 일단 오렌지 복귀는 했으니 잘한걸로..? A. DIY Wooden Ladder 가장 큰 두개를 수직선으로 삼으면 된다. B. Pillars max에서 시작해서 투포인터로 퍼저나가는 방법을 썼다. maximum이 global maximum인지 확인하는 방법이 더 좋고 편한 방법같다. n-1을 찾고 - n-2를 찾고 - ...식으로 생각해서 이런 풀이가 나왔던거 같다. 쉬운 문제여서 다행히 큰 상관은 없었다. C. Array Splitting 처음에 a_i >= a_i-1를 못보고 whining하고있었다. 조건을 잘 읽자.. division하는 operation이 cost..

https://www.acmicpc.net/problem/17353 17353번: 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 욱제의 은밀한 취미 중 하나는 매일 밤하늘을 감상하는 것이다. 😓 욱제는 하늘의 별들이 다음과 같은 규칙들을 따르며 떨어지는 걸 관찰했다. 별이 떨어지는 위치는 N개의 점이다. 점은 순서대로 1, 2, ..., N의 번호를 갖는다. 매일 밤 별들은 1, 2, ..., N의 연속한 부분 구간 [L, R]에 떨어진다. [L, R]에 별이 떨어지면, 각 점에는 순서대로 1, 2, ..., R-L+1개의 별이 떨어진다. 다시 말해, L에는 1개, L+1에는 2개 www.acmicpc.net 문제를 간단하게 말하자면, 쿼리 1: [l, r] 구간의 원소에 각각 1, 2, .....

https://codeforces.com/contest/1178/standings/participant/26499798#p26499798 결과적으로는 만족스러운 라운드였다. :) A. Prime Minister 그리디하게 가져올 수 있는 파티를 다 가져오면 된다. A번치고 문제가 길어서 읽기 힘들었다. B. WOW Factor o하나당 (좌측에 있는 w개수*우측에 있는 w개수)를 더하면 되고 왼쪽에서 오른쪽으로 순차적으로 보며 카운트를 잘 관리하는 식으로 O(n)에 풀 수 있다. C. Tiles 대회 중에는 처음에는 dp쪽으로 생각해보다가, 예제를 보고 2**(w+h)라는 식을 찍어서 냈고 맞았다.이 식이 맞다고 확신한 결정적 계기는 14분여쯤에 맞은 사람 수를 봤는데 200명이 좀 넘었다. 정말 dp였..

https://codeforces.com/contest/1195 Dashboard - Codeforces Round #574 (Div. 2) - Codeforces codeforces.com 스코어보드에 대조해 보니 대략 2070점 정도의 퍼포먼스로 보인다. 오늘 라운드도 어김없이 뇌절이 넘쳐났다. 전체적으로 실수가 좀 적었으면 좋겠다.. A: 처음부터 알고리즘은 맞았는데 n과 k헷갈려서 AC가 32분 늦어졌다. 그리고 33분 제출에서 test 17에 틀렸는데 이건 pretest에 없었기 때문에 내가 실제로 대회에 이대로 나갔으면 시스페일이였을 것이다... B: 곱셈 오버플로우때문에 한번 틀리고 시간복잡도 문제인줄 알고 binary search로 다시 써서 맞췄다. C: 간단한 DP. D: 길이 X와 길..

RTG3A로 만난 문제이다. 풀이 모든 가능한 subsequence를 다 보는 가장 간단한 브루트포스는 \(O(n\cdot 2^n)\)이다. 팀연습 중엔 여기까지밖에 생각을 못했고, 에디토리얼을 보고 내가 이해하기 편한 식으로 풀이를 한번 풀어서 써보았다. 우선 아래의 토의를 위해 \(a_i\)의 비트 개수를 \(m\)이라 하자. 즉, 이 문제에서는 \(m = 20\). 먼저 \(a_i = 0 \text{ or } 1\)인 케이스를 생각해보자. 즉 \(a\)는 bitstring of length n. 이 상황에서 bitwise and가 0이 되는 경우의 수를 찾을려면, 먼저 0인 숫자가 하나라도 subsequence에 들어가면 bitwise and는 0이 된다는 것을 생각해보자. \(a\)에 1이 \(t..

대회 링크: https://codeforces.com/contest/1194 내 블로그 첫 대회 포스팅이다! 와아!!!!! 제출 기록 + 코드: https://codeforces.com/submissions/dlwocks31/contest/1194 너무 뇌절이 넘쳐나는 라운드였고 D에서 그 정점을 찍었다. D에서 말리면 D에만 묶여있을게 아니라 E도 봤어야 하는데 D가 스코어보드상으로 너무 너무 쉬워 보여서 25분 이후로 내내 "10분만 더 있으면 D번 푼다" 상태에 있어서 E번은 문제만 읽고 생각을 해보질 않았다. 후.. A. Remove a Progression 처음에 어려워 보였는데 종이에 슥슥 그어보니까 매우 쉬운 규칙이 나와서 믿음의 제출했다. B. Yet Another Crosses Probl..

RTG3 C 로 만난 문제이다. 시도 처음 봤을 때는 n이 작으니 어떻게든 모든 가능한 트리를 다 순회해보면 되지 않을까? 하는 생각이 들었다. 모든 가능한 parent assginment를 다 시도해보면 \((n-1)^{n-1}\)이라 안되고, 트리에 dfs in/out기록을 토대로 만들 수 있는 2n짜리 bracket sequence? 같은걸 순회해볼 생각도 했다. 이건 \( n\cdot 2^{2n-2} \) 정도의 비벼볼만한 시간복잡도가 나오는데 이렇게 카운트하면 children의 순서가 바뀌면 다른 트리로 카운트된다는 것을 깨닫고 그 중복을 없애볼 생각을 하다가 너무 어려워서 포기했다. 풀이과정 우선 풀이의 첫 몇줄에서 (\(dp_{i, bm}\) = i를 루트로 하고 bm(bitmask의 약자)..