PS 일지

Codeforces Round 914 (Div. 2)에 참가했다.요즘 시간대가 안 맞아서 참여하지 못했었는데, 1600점을 달성하겠다는 강한 의지를 가지고 드디어 참가했다.이번에도 3솔따리인가 싶었는데 운 좋게 3솔은 면했다. A - Forked! (00:09) 변형 나이트가 $(a, b)$만큼의 칸을 움직일 수 있을 때, 이동 한 번으로 두 좌표에 모두 도달 가능한 칸의 개수를 세는 문제다. map으로 구현했는데, $a = b$인 경우를 빼느라 구현하는데 시간이 오래 걸렸다. B - Collecting Game (00:19) 수들을 모두 최소 PQ에 넣고 하나씩 빼면서 해당 수로 가능한 최대 개수를 구해줬다. C - Array Game (00:31) 우선, $k \ge 3$인 경우에는 ..

12/1 ~ 12/10에 푼 문제들입니다.문제의 풀이가 포함되어있으니 유의하세요. 12/1BOJ 1911 - 흙길 보수하기Gold 5 #sorting #greedy 웅덩이들을 $x$좌표 기준 오름차순으로 정렬해놓고, 변수 $t$를 (마지막 널빤지가 덮고있는 끝 지점 +1)로 유지하며 관리하자.어떤 웅덩이 $[S, E)$에 대해, 그 웅덩이를 모두 덮기 위해 필요한 널빤지 수는 다음과 같다. $\lfloor \dfrac{E - \max(t, S) - 1}{L} \rfloor + 1$ 단, 마지막 널빤지가 그 웅덩이 전체를 포함하는 경우는 예외다.BOJ 30037 - K-Words ProblemGold 3 #implementation #string 문장 하나를 getline으로 받아서 2번 규칙을 가..

11/21 ~ 11/30에 푼 문제들입니다.문제의 풀이가 포함되어있으니 유의하세요. 11/22BOJ 18251 - 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy)Platinum 4 #dfs #sweeping 깊이를 기준으로 스위핑을 하면 된다.$0 \le i \le j \le \log_2{N}$인 $i, j$에 대해, 깊이 $i$ 이상 $j$ 이하의 모든 점을 탐색하며 최대 연속합을 구하자.이 스위핑+탐색이 문제에서 요구하는 직사각형을 그려보는 것에 해당한다.연속합은 트리를 inorder 순서로 펴서 구해도 되는데, 본인은 금광 테크닉으로 구했다.BOJ 16877 - 핌버Platinum 3 #sprague_grundy 스프라그-그런디 정리로 해결하면 된다.m..

Codeforces Round 910 (Div. 2)에 참가했다.예상했던 것보다 훨씬 어려워서 놀랐다. 풀다가 벽에 막힌 느낌이 강하게 들었고, 문제도 얼마 풀지 못해서 처음으로 레이팅이 떨어질까 걱정했다. A - Milica and String00:05 AC 항상 1회 이하의 연산으로 가능하다.B의 개수를 세서 $k$보다 클 때, 같을 때, 작을 때로 분류해서 처리하면 된다. B - Milena and Admirer00:23 AC 어떤 수를 쪼갤 때, 어떻게 해야 최적인지의 여부는 뒤에 존재하는 수들에 따라 달라진다. 따라서, 뒤에서부터 본다는 접근은 자연스럽다.$a_i > a_{i+1}$인 $i$에 대해, $a_i$를 모두 $a_{i+1}$이하인 수들로 나눠야 한다.이 때 수행해야 하는 연산 횟..

11/11 ~ 11/20에 푼 문제들입니다.문제의 풀이가 포함되어있으니 유의하세요. 11/11BOJ 10216 - Count Circle GroupsGold 4 #geometry #disjoint_set $O(N^2)$에 간선을 생성해주고, 컴포넌트 개수를 세주면 된다.11/12BOJ 30510 - 토마에 함수Gold 1 #Euler's_totient_function $1 + \sum \limits_{i=1}^{\lfloor \frac{Q}{P} \rfloor} \phi{(i)}$을 구해주면 된다.11/13BOJ 14451 - 안대 낀 스피드러너Platinum 5 #bfs 위를 보는 상태와 오른쪽을 보는 상태를 시작으로, 두 점을 동시에 움직이며 bfs하면 된다.상태 1의 $x, y$좌표 및 방향, ..

제1회 스타보우컵에 참가했다. 누워서 뒹굴거리다가 시간을 보고 뒤늦게 참가했다. Red - 이 별은 무슨 색일까 00:31 AC if-else를 쓸 줄 아는가? 라는 문제다. Orange - 반짝반짝 빛나는 별가루 00:38 AC 시뮬레이션(?)같은 단순 계산 문제다. 요소가 많아서 생각보다 푸는 데 오래 걸렸다. Yellow - 별 가두기 00:45 AC 진짜 시뮬레이션 문제다. 별을 직접 움직여보고 같은 칸에 같은 방향을 가지고 있을 때가 있다면, 가두기에 성공한 것이다. Green - 별 안에 별 안에 별 찍기 01:02 AC 문제를 보자마자 한숨을 쉬었다. 3125 * 3125 크기의 공간을 미리 잡아두고, 재귀로 칸들을 채워줬다. Blue - 별자리 만들기 01:19 AC 처음에 주어지는 트리는..

Codeforces Round 909 (Div. 3)이번 라운드는 여러모로 아쉬운 게 많은 대회였다... 못 푼 문제들이 다 뭔가 아쉽게 놓친 듯한 느낌이 들어서였다.못 한 만큼 더 열심히 공부해야겠다. B - 250 Thousand Tons of TNT00:08 AC $N$이 $K$로 나누어떨어지는 모든 경우에 대해 확인해보면 된다. 누적 합을 곁들이면 어떤 $K$에 대해 $O(\frac{N}{K})$의 시간이 걸린다. A - Game with Integers00:02 WA 00:09 AC $N$이 3의 배수이면, 반드시 선공이 진다. 선공이 3의 배수에 +1 혹은 -1을 해도 후공이 다시 3의 배수로 만들어버리면 선공은 영원히 3의 배수를 만들지 못하기 때문이다.반대로 $N$이 3의 배수가 ..

2023 Sogang Programming Contest Open (Master)에 참가했다. 전날에 열렸던 Arena #11을 놓쳐서 이번에는 꼭 해야지 생각하며 등록을 하고 잔 것 같았는데, 일어나보니 등록이 안되어있었다. 아레나는 언제쯤 참가할 수 있을까.. A - Knob00:06 AC 직전의 $L, R$ 값을 갖고 있으면서 매번 확인해주면 된다. B - donstructive00:10 AC $1, N, 2, N-1, \cdots$ 순으로 배치하면 된다. C - 내 집 마련하기00:23 AC $L, R$에 해당하는 인덱스를 정렬시켜 $L$부터 $R$까지 사람에 대해 재배치하면 된다. D - 서로소 싫어00:39 WA 00:39 WA 00:40 AC $x$를 $xy$로, $xy$를 $y..

2023 IGRUS Newbie Programming Contest Open에 참가했다. Arena #11이 끝나고 바로 열려서 1솔만 하고 가신 분들이 많은 것 같다. A - 아이그루스와 화장실00:21 AC $K-1, K, K+1$중 적절한 곳으로 보내주면 된다. B - 트릭 플라워00:28 AC R의 제한이 작아서 직접 시뮬레이션하면 된다. C - 인형 전시00:33 WA 00:38 WA 00:38 AC 높이가 작은 것부터 한 열에 하나씩 채워주면 된다. 배치했을 때 가려지는 것이라면, 채우지 말고 건너뛰어야 한다.첫 WA는 구현 실수, 두 번째 WA는 코드 한 줄을 실수로 지우고 내버려서 떴다. D - 회문 끝말잇기02:00 WA 02:02 AC 게임 특성상, 시작 알파벳과 끝 알..

SASA Programming Contest 2023 Open Contest Div. 1에 참가했다. 아레나에 참가하고 싶었는데, 시간이 늦어서 등록을 못 했다. A - 방형구 탐색00:36 AC 쿼리를 naive하게 $O(N)$으로 구현하면 총 시간복잡도 $O(NQ)$로 통과한다. B - 미역은 식물 아닌데요00:40 AC 어떤 식물 $i$에 대해,$P == 1$이면서 $M == 0$인 것은 항상 식물이다.$P == 0$이거나 $M == 1$인 것은 항상 식물이 아니다.그 외의 것들은 식물이 될 수도 있고, 되지 않을 수도 있다. C - 가위 가위 가위00:47 WA 00:48 AC $1 \le i \le 100$에 대해, $i$번째에만 주먹을 내고 나머지는 모두 가위를 내서 대결을 총 100번..