PS 일지

Round 917에서 내 실력에 허무함을 느끼고 한동안 PS를 하지 않았었다. 그러다 블루 복귀를 위해 간절함을 가지고 다시 시작하게 되었다. A - Square (00:02) 네 개의 점이 사각형을 이루는 것이 보장되므로 네 점에 대한 $x$, $y$좌표의 최소, 최댓값을 구해 놓으면 넓이를 구할 수 있다. B - Arranging Cats (00:08) 두 수열에 대해 같은 인덱스끼리 xor을 해주고 다시 저장하면, 변화를 줘야 하는 박스들만 남는다. 두 수열에서 남은 $1$의 수 중 최댓값 만큼의 작업으로 두 수열을 같게 만들 수 있다. C - Sending Messages (00:16) $m_i$에서 $m_{i+1}$로 갈 때, 폰을 껐다가 다시 키는 경우와 쭉 켜두는 경우 중 더 작은 값에 해당..

이번 라운드가 역대 최저점 퍼포먼스를 찍은 라운드였다... A번을 풀고 B를 보는데 풀이가 바로 생각나는 게 없어서 나머지 문제들을 둘러봤다. E를 풀 수 있을 것 같아서 여기에 시간을 다 쏟아부었는데, 왜 틀리지 하다가 반례가 생각났고 고칠 수 없어서 그냥 포기해버렸다. A - Least Product (00:04) 배열에 $0$이 있거나 음의 원소 개수가 홀수이면, 아무런 작업을 하지 않았을 때 전체 곱이 최소가 된다. 그렇지 않으면, $0$이 아닌 원소들 중 아무 원소에 작업을 1회만 하면 전체 곱이 최소가 된다. B - Erase First or Second Letter ??? C - Watering an Array ??? D - Yet Another Inversions Problem ??? E ..

Codeforces Round 915 (Div. 2) 에 참가했다. 이번 라운드는 내 안일한 판단때문에 아쉬웠던 라운드였다. 무지성 제출을 하면 안 된다는 걸 배워가는 좋은 기회라고 생각해야겠다. A - Constructive Problems (00:04) 문제가 $n\times n$ 정사각형일 때를 생각해보면, 답은 $n$임을 쉽게 알 수 있다. $n\times m$ 격자에서, 우선 $\min(n, m)$ 크기의 정사각형을 모두 build할 수 있다. 남은 직사각형의 크기가 $x \times y$ 라면, $\min(x, y)$ 크기의 정사각형을 또 모두 build할 수 있다. $\vdots$ 이 과정을 반복해서 정답을 구하면 $\max(n, m)$이 된다. B - Beginner's Zelda (00:..

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$인 경우에는 답이 무조건 ..

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

제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 TNT 00:08 AC $N$이 $K$로 나누어떨어지는 모든 경우에 대해 확인해보면 된다. 누적 합을 곁들이면 어떤 $K$에 대해 $O(\frac{N}{K})$의 시간이 걸린다. A - Game with Integers 00:02 WA 00:09 AC $N$이 3의 배수이면, 반드시 선공이 진다. 선공이 3의 배수에 +1 혹은 -1을 해도 후공이 다시 3의 배수로 만들어버리면 선공은 영원히 3의 배수를 만들지 못하기 때문이다. 반대로 $N$이 3의 배수가 ..

2023 Sogang Programming Contest Open (Master)에 참가했다. 전날에 열렸던 Arena #11을 놓쳐서 이번에는 꼭 해야지 생각하며 등록을 하고 잔 것 같았는데, 일어나보니 등록이 안되어있었다. 아레나는 언제쯤 참가할 수 있을까.. A - Knob 00:06 AC 직전의 $L, R$ 값을 갖고 있으면서 매번 확인해주면 된다. B - donstructive 00: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$번째에만 주먹을 내고 나머지는 모두 가위를 내서 대결을 총 10..