PS 일지

BOJ의 서비스 종료 소식을 접하고 많은 생각이 들었다. 어떤 분야에 이렇게 열정을 쏟아서 공부해본 적이 처음이었다.문제 하나를 풀 때마다 느껴지는 성취감 자체가 당시의 나에겐 가장 큰 즐거움이었다.알고리즘 문제 풀이에 재미를 느끼게 해줬다는 것 외에도 많은 것을 줬던 것 같다. 처음 시작할 때는 스터디에 들어가서 열심히 배우는 입장이었지만, 나중에는 내가 스터디의 멘토로서 지식을 공유할 수 있었다. 같이 팀 대회에 출전하여 머리도 꽁꽁 싸매보고, 이틀 밤낮에 걸쳐가며 하나만 붙잡고 풀어도 보고, 문제가 잘 안 풀릴 때는 짜증도 내보고, 대회에 직접 문제를 출제도 해봤다. 내가 처음 냈던 문제가 처음 풀렸을 때의 기분은 아직도 잊을 수 없다. 여러 활동을 한 덕분에 감사하게도 그 안에서 다양한 사람들을..

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 - Co..

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 String00:05 AC 항상 1회 이하의 연산으로 가능하다.B의 개수를 세서 $k$보다 클 때, 같을 때, 작을 때로 분류해서 처리하면 된다. B - Milena and Admirer00: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 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 게임 특성상, 시작 알파벳과 끝 알..