상위 99.99%의 PS

21, 22일은 여행 이슈 BOJ 25488 - 토큰 (P4) 더보기 scc에 속하는 토큰의 개수가 같은 채로 유지되어야 문제의 조건을 만족한다. BOJ 23268 - Deceptive Directions (G2) 더보기 일단 bfs로 가능한 보물의 위치는 주어진 문자열을 통해서 대충 구해놓을 수 있다. 그러나, 경로는 무조건 최단경로여야 하므로 각 셀의 거리를 전처리하면 된다. BOJ 17625 - 고압선 (D2) 더보기 점 a, b, c에서 선분 ab와 점 c의 거리, 또는 어떤 두 점 사이의 거리 중 최대/2를 구해야 하는데, 어떤 두 점을 잇는 선분에서, 이와 수직인 선분을 지나는 다른 점은 존재해서는 안 된다. 이는 한 점을 90도를 돌리면 된다. 이거를 불도저로 구하면 끝이다. BOJ 1649..

개강 전까지 1000솔 찍기라는 목표를 달성했다. 하지만 실력은 오르지 않는 기분이다. BOJ 8188 - Intelligence Test (G1) 더보기 수열 b의 첫 번째 윈소부터, A에서 찾아주면 된다. 가장 왼쪽에서 채워야 하니 각 수마다 인덱스 배열을 만들어줘서 이를 찾아주면 된다. BOJ 2988 - 아보가드로 (P2) 더보기 한 쪽을 고정하고, 다른 두 배열에서 사라지는 수들을 다시 고정된 배열에서 확인하며 지워나가는 방식으로 풀면 된다. bfs 느낌..? BOJ 8221 - Letters (P5) 더보기 inversion의 개수를 세는 문제이다. BOJ 2162 - 선분 그룹 (G1) 더보기 선분 교차 + DSU로 풀린다. 마지막에 부모 압축을 해주어야 함에 유의. BOJ 3648 - 아이..

BOJ 9007 - 카누 선수 (G3) 더보기 MITM 기초문제이다. BOJ 9010 - Möbius Strip (G3) 더보기 가로와 세로를 따로 계산할 수 있다. 식 정리는 매우 깔끔하게 나온다. BOJ 9011 - 순서 (G5) 더보기 R_n부터 거꾸로 돌아가며 배열을 채워주면 된다. N이 작아서 가능함 BOJ 22348 - 헬기 착륙장 (P4) 더보기 dp[r][a] = 반지름이 r이고 어떤 색의 페인트를 a만큼 사용했을 때의 경우의 수로 정의하자. 이 dp의 누적합을 또 만들어 주고 각 쿼리를 O(1)에 구하면 된다. BOJ 1071 - 소트 (P5) 더보기 문제가 하라는 대로 O(N^2)로 풀면 된다. 단순 구현 BOJ 2320 - 끝말잇기 (G1) 더보기 dp[l][r][bit] = 왼쪽과 ..

BOJ 10883 - 분할 (P3) 더보기 행과 열 각각에 대하여 bfs를 돌려주자. 각 단계마다 1*K꼴의 사각형이 존재하는지 확인하고, (1의 개수)*(K의 개수)를 ans에 더해주면 된다. 각 분할의 단계마다 상태는 최대 2가지 존재할 수 있어서 터질 걱정은 안 해도 된다. BOJ 22984 - 반짝반짝 2 (G5) 더보기 기댓값의 선형성. 일단 사이에 추가된 전구를 무시하는 경우는 단순히 \(p_i\)를 다 더하면 되고, 추가된 전구가 켜질 확률은, 이웃한 두 전구 중 하나만 켜질 확률과 같다. 이 확률을 \(sum(P)\)에 더해주면 된다. BOJ 4354 - 문자열 제곱 (P5) 더보기 kmp의 실패함수를 이용하자. fail[s-1]이 \(\frac{ s(k-1) }{ k }\) 꼴이어야 한다..

풀이를 구체화하는 능력이 너무 부족하다..... 1 - 수열연산 투 포인터로 가장자리부터 깎아주면 된다. 2 - 반 협동게임 각 수 별로 가장자리부터 깎아서 순서쌍들을 다 모으자. 이를 정렬하고 왼쪽부터 보면 된다. 배열 크기를 잘못 잡아서 6번이나 제출을 날렸다. 이거때문에 멘탈이 흔들렸다. 3 - ABC dp[x][c][k] = x번 정점에서 알파벳이 c이고 k번 스킵했을 때의 최대 길이로 정의했지만, 여기서 사이클 찾기랑 막 뇌절하면서 그대로 침수.. k=0인 경우만 긁었다. 4 - 직사각형 1x1 사각형에서 NxN까지 늘리려면, 어자피 2N-1번만 늘리면 된다. O(N^3)에 가능하다. 근데 이를 깨닫지 못했다. 어떤 수 x와 y에 대해, y - x + 1와 x~y의 수들을 모두 포함하는 최소 직..

CodeTON Round 2 -11을 받을 예정이다. 아마도 A b의 첫글자를 제외한 나머지는 a의 맨 뒤에 있어야 한다. 그리고 b의 첫글자는 a의 남은 앞에서 찾으면 된다. B 어떤 구간에서, max - min > 2x 면 불가능한 경우이다. C 나누어지는 구간의 크기를 찾고, 가장 큰 구간부터 먹으면 된다. i번째에서는 size[i] - (4i - 3)만큼 먹을 수 있으니, 이를 ans에 더해주자. 다만, 값이 음수면 그냥 넘어가고, 0이면 1을 더해주면 된다. n - ans가 답이다. D 첫 배열을 강제해보자. operation 1을 거꾸로 해주면서, 투포인터로 처음 배열의 상태를 찾을 수 있다. 이들 중 다른 하나가 operation 2를 사용한 배열이다. 이때 1번 연산의 처음 배열과, 2번 ..

kmp 공부 해야되는데.. BOJ 19586 - 울타리 (D5) 더보기 2차원 평면의 점에서 가장 거리가 먼 두 점은, Rotating Calipers를 이용하여 구할 수 있다. 이를 응용해서 90도와 270도 방향의 직선을 찾을 수 있다. 벡터의 내적과 외적을 이용하면 된다. BOJ 11000 - 강의실 배정 (G5) 더보기 스위핑?처럼 풀 수 있다. 구간 \([l, r]\)에서 \(l\)에는 +1, \(r\)에는 -1을 해주고, 쭉 훑으면서 최댓값을 찾으면 된다. BOJ 25392 - 사건의 지평선 (D4) 더보기 \(a_i\)가 담당하고 있는 구간 \([l, r]\)에 속하는 수들에 간선을 쭉 보내주자. 어느 순간부터 수가 일정하게 반복된다는 것은, 어떤 정점이 간선을 타고 가다가 scc에 들어가는..

난이도 조절 실패 + 1E 유출 (BOJ 23679에서 볼 수 있다)의 환장의 콜라보... A (00:02) 2, 3, ... , n, 1 B (00:50) m이 짝수면 0이므로 홀수인 경우만 생각해보자. pair 하나를 제거하는 경우는 그냥 세고, pair에 포함되는 사람 하나를 제거(?)하는 경우는, cnt[i]가 홀수인 경우에만 가능하다. C (00:24) 2 이상의 k에 대해, k×N 또는 k×M으로만 자를 수 있다. D (--:--) 봉우리의 값은 O(N)에 구할 수 있다. 여기서 m을 초과하는 것만 봐서, 다른 것들과 합쳐주자. 그렇게 B_i가 i번째에서 빼야 하는 값을 가지도록 하면 된다. P_i와 비교해서 답 여부를 찾아주자. 근데 구현량이 너무 많아서 시간 이슈로 풀지 못했다. 잡소리긴 ..

패널티 기계가 되었다. 만족할 만한 결과를 내지 못했다.. 스코어보드는 아직 못 보는듯..? 우리 팀은 4솔(+10)로 43등정도를 했다. 오프라인 대회가 처음이라 그런지, 이런 어수선한 분위기에 적응이 되지 않았다. 게다가 잘 시간인 6시 쯤에 일어나니 더 피곤했다. 구차한 핑계는 넘기고.. 문제를 많이 못 푼 만큼, 풀이도 매우 간단히 적겠다. H (solved by me, +1) 뒤가 큰 것부터 먹고, 그 다음 앞이 큰 것을 먹으면 된다. J (solved by greedev, +3) 답은 1 또는 2이다. 1인 경우는 쉽고, 아닌 경우에는 l r 각각 존재 여부를 찾아주면 된다. K (solved by greedev, +3) 구현이 매우 빡세다. 지는 횟수와 이기는 횟수를 잘 보면 된다. 구현을 ..

어제는 ucpc, 오늘은 icpc 팀연습을 했다. 힘들다. 심지어 오늘은 몸살 기운 때문에 컨디션이 너무 안 좋아서 팀연습 때 트롤을 했다.. BOJ 20191 - 줄임말 (G2) 더보기 문자열의 i번째 글자의 위치를 이분 탐색으로 찾아주면 된다. BOJ 3654 - L퍼즐 (D5) 더보기 어떤 B에 대해, 상하를 true/false로 두고, 좌우를 true/false로 두자. 그리고 B와 연결된 W에 대해, 이 W와 연결된 B에 대해서도 논리식을 세워주면 된다. 나는 2-sat을 연습하기 위해 이렇게 풀었는데, 단순 bfs로도 풀린다고 한다. BOJ 14961 - Untangling Chain (P5) 더보기 i번째에, (i-1)번째와 동일한 방향으로 회전하는 경우라면 i칸을 이동하고, 아니라면 1칸을..