pizzaroot

PS에서 시간복잡도는 매우 중요하다. 시간복잡도는 보통 Big O notation으로 나타낸다. 그래서 시간복잡도가 무엇인가? PS에서 시간복잡도는 문제를 해결하는 데에 걸리는 시간을 입력 크기를 나타내는 변수(들)로 나타낸 함수이다. 하지만 우리가 관심을 가지는 것은 최악의 경우이다. Big O notation의 formal한 정의를 설명하자면 만약 모든 실수 \(x>x_0\)에 대하여 \(f(x)\leq cg(x)\)를 만족하는 실수 \(x_0\)와 양의 실수 \(c\)가 존재한다면, \(f(x)\in O(g(x))\)로 표현한다. 정확하게는 \(O(g(x))\)는 함수들의 집합이지만 다음과 같이 많이 나타낸다. \[f(x)=O(g(x))\] 다른 표기법도 존재하지만 Big O notation을 거의..

후기는 밥먹고 씀

먼저 \(N\)이 \(10\,000\)까지 들어오는 것을 보아서 각 선풍기마다 시간 간격만큼씩 더해가며 시뮬레이션 하는 풀이는 통과하기 힘들것이라는 짐작이 벌써 든다. 각 선풍기 마다 \(O(1)\)만에 가격을 구하는 풀이도 존재할 것 같지만, 일단은 쉽게 구현한다는 생각이 들어서 이분탐색을 떠올리게 된다. 대충 구상을 했으니 이제 코드를 짜기 시작한다. 라고 생각하고 코드를 짜다보니 시간이 이미 주어지므로 이분탐색이 전혀 필요 없다는 사실을 깨닫게 된다. 그렇다면 총 몇번을 추가 결제 해야 하는가를 구할 때 \(\displaystyle\left\lfloor\frac{Q}{K}\right\rfloor\)번인지 \(\displaystyle\left\lceil\frac{Q}{K}\right\rceil\)번인..

D번: 중요한 #include #define INF 0x7fffffff #define SIZE 100001 using namespace std; int seg[SIZE > 1; i > 0; i >>= 1) seg[i][id] = min(seg[i >= 1) { if (l & 1) ret = min(ret, seg[l++][id]); if (~r & 1) ret = min(ret, seg[r--][id]); } return ret; } int pos(int val, int right) { right += SIZE; while (seg[right][0] > val) right = (right - 1) >> 1; while (right k; int v, w; ci..

\(O(n^2)\) #include #include #include int main() { int n, ans = 0; scanf("%d", &n); int *arr = (int *)malloc(n * sizeof(int)); assert(arr != NULL); for (int i = 0; i < n; i++) scanf("%d", arr + i); for (int i = 0; i < n; i++) { int good = 1; for (int j = 0; j < i; j++) { if (arr[j] == arr[i]) good = 0; } ans += good; } printf("%d\n", ans); return 0; } \(O(n\log n)\) #include #include #include vo..

모두 수고하셨습니다!

경과 타임라인 문제 킬 어시스트 10분 [B] Commemorative Dice pizzaroot 적을 처치했습니다! 32분 [C] Dessert Café WA 38분 WA 연속 킬 차단! 48분 [E] Imprecise Computer pizzaroot 더블 킬! 58분 [C] Dessert Café WA 71분 WA 78분 WA 제압 되었습니다! 98분 [J] Switches WA 108분 [C] Dessert Café wlsth1004100 3juhwan 아군이 적을 처치했습니다! 116분 [J] Switches pizzaroot 트리플 킬! 160분 [G] Mobile Robot WA 174분 pizzaroot 3juhwan / wlsth1004100 쿼드라 킬! 풀이 [B] Commemorati..

E번을 13분에 내가 풀었다. A번을 20분에 내가 아닌 사람이 풀었다. C번을 50분에 내가 아닌 사람이 풀었다. K번을 141분에 내가 아닌 사람이 풀었다. G번을 내가 잡다가 결국 못 풀었다. F번을 내가 아닌 나머지가 잡다가 결국 못 풀었다. 너무 너무 아쉬워서 집가서 ACEF를 봤는데 너무 쉬워서 당황했다. 너무 너무 너무 아쉽다. 본선에 나가게 된다면 팀연습이 더욱 필요할 것 같다.

\(\mathrm{dp[}i\mathrm{][}j\mathrm{]}\)는 구간 \((i, j]\)의 문자열에 대한 답과 그 문자열을 최대 몇개의 동일한 부분 문자열로 분할할 수 있는지를 저장한다. \(\mathrm{dp[}i\mathrm{][}i\mathrm{]=1}\) \(\displaystyle\mathrm{dp[}i\mathrm{][}j\mathrm{]}=\min_{k=i+1}^{j-1}\mathrm{(dp[}i\mathrm{][}k\mathrm{]}+(0\:\mathrm{or}\:\mathrm{dp[}k\mathrm{][}j\mathrm{]))}\) 구간 \((i, k]\)문자열과 \((k, j]\)문자열의 반복된 부분이 같다면 \(\mathrm{0}\) 그렇지 않으면 \(\mathrm{dp[}k..

\(x\)를 먼저 구한 후, 이분탐색을 통해 \(y\)를 구한다. \(\displaystyle\sum_{k=1}^{n}k^5\)은 \(O(1)\)시간에 구할 수 있다. Python으로 풀면 편하다. p, q = map(int, input().split()) def f(n): return n ** 2 * (2 * n ** 4 + 6 * n ** 3 + 5 * n * n - 1) // 12 i = 1 while True: if p