상위 99.99%의 PS

민트가 되었다. 나쁜쪽으로 문제셋? 컨셉을 이런식으로 잡는걸 볼때마다 뭔가 화난다. 이런 것들을 코포에서까지 보고싶지는 않다 A (00:06) 처음으로 나오는 1과 0의 위치를 이용해서 풀면 된다. B (00:12) 홀수가 존재한다면 짝수의 개수가 답이다. 존재하지 않는다면 가장 적은 횟수로 홀수를 만들 수 있는 짝수 k를 찾고, 그 횟수를 c라고 할 때, c + even_cnt - 1이 답이다. C (--:--) 알파벳의 등장 횟수가 홀수인 알파벳이 답이다. 게임하다가 갑자기 번뜩 떠올랐는데, 진짜 허무하다. 업솔빙한 기분도 들지 않는 개쓰레기 문제 D (--:--) k=n일 때는, n분이 남을 때까지 한쪽 끝에서 기다렸다가 반대쪽 끝으로 이동하면 된다. 이것보다 나은 정답은 존재하지 않는다. 실력은...

6월 1일에 더 문제를 풀 생각이 없었는데 dong_gas의 문제 추천 세례를 받고 과솔빙을 했다..ㅎ 덕분에 문제들이 순식간에 쌓였다 BOJ 24654 - Build The Grid (G2) 더보기 달팽이처럼 빙글뱅글 돌리면 된다 BOJ 2041 - 숫자채우기 (D5) 더보기 이게 왜 다5인지 모르겠다. 가로를 +1, -2, +3, -4, ... 로 채우고, 세로는 역순으로 채우면 된다. BOJ 19217 - Jitterbug (D3) 더보기 두 그룹으로 나누어보자. 한 쪽 정점 100개 그룹은 모든 정점끼리 연결하고, 나머지는 일자로 만들면 된다. 이 둘을 잇기만 하면 된다. BOJ 21099 - Four XOR (P5) 더보기 두 값을 XOR한 값은 많아봤자 2^17개이다. 비둘기집 원리에 따라서 ..

다행히도 요즘은 스트레스를 덜 받나보다. 어제 코포 레이팅을 -50정도 받았는데도 화가 안났다. 오늘부터 플3~다5 랜덤디펜스를 시작했다. 마지막 두 문제는 오늘 푼 것임 BOJ 17473 - 수열과 쿼리 25 (R5) 더보기 세그비츠 문제다. 이 글로 풀이를 대체함 BOJ 2268 - 수들의 합 7 (G1) 더보기 세그트리 슈퍼기초문제다. \(i > j\)인 쿼리가 들어올 수 있음에 유의하면 된다. BOJ 17476 - 수열과 쿼리 28 (D1) 더보기 세그비츠 활용문제다. 제곱근 값은 빠르게 감소하는 특징이 있으므로 같은 값을 가지는 리프노드들이 많아지게 된다. 그러나 \([100, 99, 100, 99, ...]\)와 같은 경우에서, 제곱근 연산과 전체 구간 \(+90\)이 번갈아 들어오는 경우가 ..

삽질하던 도중 깨달음을 얻고 코드를 갈아엎고 AC.. 수쿼26보다 훨씬 직관적이었지만 그 내용은 훨씬 어려웠다. 간단히 풀이를 적자면, OR쿼리에서 k의 켜진 i번째 비트에 대해 구간의 i번째 비트가 모두 꺼져있을 때만 갱신하면 된다. AND쿼리도 비슷하다. 나는 세그트리에 max, or, and값을 저장하고 풀려고 했는데, or과 and 대신 그냥 구간 내에서 모두 켜진 비트와 꺼진 비트들을 저장하는 것이 편할 것 같아서 그렇게 했다. 사실 별 차이는 없고, 코드에 대한 가독성이 이게 훨씬 좋아서 디버깅에도 도움이 많이 되고 그랬다.. or과 and를 쓰는 코드를 다시 보니, 헷갈려서 잘못 쓴 부분들이 많았다. 나는 스도 코드(pseudo code)를 잘 쓰지 않는 습관이 있고, 이게 독이 되었다. 코..

https://www.acmicpc.net/problem/17474 17474번: 수열과 쿼리 26 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 L R X: 모든 L ≤ i ≤ R에 대해서 Ai = min(Ai, X) 를 적용한다. 2 L R: max(AL, AL+1, ..., AR)을 출력한다. 3 www.acmicpc.net [알고리즘 분류] Segment tree beats greedev에게 세그비츠가 웰논인지 물어봤는데, 다음과 같은 답변을 받았다. (수쿼 25~30은 모두 세그비츠를 사용한다고 한다.) 나는 정말 무식하지만, 최대한 열심히 설명해보도록 하겠다. 나보다 설명을 몇십배는 잘 해둔 글이 수두룩하기 때문에, 나의 글로..

주식회사 승범이네를 제외한 7문제. 그냥 6문제정도 쌓일 때마다 글을 올려야겠다. 귀찮아질 것 같아서... BOJ 16679 - Back to the Bones (P5) 더보기 전처리 dp 문제이다. \(dp[i][k] = \)(i번째에서 주사위들의 눈의 합이 k가 나오는 경우의 수)라고 정의해보자. 주사위 \(x\)개를 다시 굴린다고 하면 눈이 가장 작게 나온 것들을 굴리는 것이 무조건 이득이다. 즉, y=(얻어야 하는 수)로 정의하면, \(dp[x][y]\)를 활용해 주사위를 몇 개 굴리는 것이 최적인지를 찾아내면 된다. 따라서 각 쿼리마다 \(O(N^2)\)에 해결할 수 있고, 전체 시간복잡도는 \(O(N^3)\)이다. BOJ 12844 - XOR (P3) 더보기 레이지 세그 활용문제이다. 홀수/짝..

https://www.acmicpc.net/problem/16404 16404번: 주식회사 승범이네 첫 번째 줄에 승범이를 포함한 판매원들의 수 N(1 ≤ N ≤ 100,000), 명령의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 판매원들은 1번부터 N번까지 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 판 www.acmicpc.net [알고리즘 분류] Segment Tree (with lazy propagation) Euler Tour Technique 오일러 경로 테크닉이라는걸 배우고, 기초문제를 풀어보았다. 오일러 경로 테크닉은 루트가 있는 트리에서 어떤 정점의 서브트리에 속하는 정점들을 연속된 수로 renumbering할 수 있는 기술이다. 일단 나는 이렇게 이해했고, 이 문제는..

과제 이슈때문에 골드 이하로만 풀었다. 근데 왜이리 어렵지? BOJ 24270 - 미니 버킷 리스트 (G4) 더보기 이게 골4 난이도인지는 잘 모르겠다. \((N + 1)\)개의 구간에 아무것도 안 하는 단위시간 \(K - sum(S)\)개를 채우는 문제이고, \(_{N+1}H_{K-sum(S)}=_{N+K-sum(S)}C_{N}\)을 계산하는 문제가 된다. BOJ 24269 - 랜드마크 건설 (G2) 더보기 Case Work. 직사각형의 테두리에 건물 3개를 짓는 것으로 접근하면 된다. 직사각형의 가로와 세로의 길이는 \(\frac{a+b+c}{4}\)를 올림, 내림한 값으로 정할 수 있다. BOJ 16681 - 등산 (G2) 더보기 보자마자 다익스트라 문제인건 알았는데, 무지성으로 다익스트라를 돌리면..

17940 - 지하철 (G2) 환승 비용을 10^6으로 잡고 다익스트라를 돌리면 된다. (N-1) * 1000 < 10^6이어서 가능하다. 2159 - 케익 배달 (G2) dp[n][k]를 n번째에서, k의 위치(상하좌우+원위치)에 있을 때의 최소 거리라고 정의하면, \(dp[i][j] = min(dp[i][j], f(i + 1, k, nx, ny) + |nx - x| + |ny - y|)\)라는 식이 나온다. 21757 - 나누기 (G3) 누적 합을 이용하면 된다. dp[n][k]를 n번째에서 나눈 구간의 개수가 k개일 때의 경우의 수라고 정의하면, \(0 \leq k \leq 3\)에서 해결할 수 있다. \(dp[i][j] = dp[i - 1][j]\)는 편안함을 위해 써두고, 추가적으로는 \(sum..

내 실력에 회의감을 느끼고 한탄하는 글이다. 최근에 4개? 라운드를 개판치고 1790에서 1627까지 떨궜다. 그래도 오늘 있던 라운드에서 81점을 올렸는데, 그래도 짜증이 났다. 20분에 3솔을 하고 나머지 시간동안 D를 풀지 못했다. 4솔을 못해서 짜증이 났다. 나는 만족스러운 결과가 나오지 않고 레이팅이 오르면 내가 못해서 화가 나고, 레이팅이 떨어지면 잃은 레이팅때문에 화가 난다. 특히 레이팅은 너무 힘이 빠지는 요소이다. 코드포스 레이팅이 게임 랭크점수처럼 정직하게 k점씩 왔다갔다 하는 것도 아니라서 복구가 금방 되지만, 이 사실을 되뇌인다고 해서 내가 받는 스트레스가 줄지는 않더라. 심지어, 레이팅과 별개로 내 실력이 정말로 오르고 있는지도 모르겠다. 청정수컵에서는 개쌉웰논 G번도 자꾸 삽질했..