PS 일지

11/11 ~ 11/20에 푼 문제들입니다. 문제의 풀이가 포함되어있으니 유의하세요. 11/11 BOJ 10216 - Count Circle Groups Gold 4 #geometry #disjoint_set $O(N^2)$에 간선을 생성해주고, 컴포넌트 개수를 세주면 된다. 11/12 BOJ 30510 - 토마에 함수 Gold 1 #Euler's_totient_function $1 + \sum \limits_{i=1}^{\lfloor \frac{Q}{P} \rfloor} \phi{(i)}$을 구해주면 된다. 11/13 BOJ 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 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..

11/1 ~ 11/10에 푼 문제들입니다. 문제의 풀이가 포함되어있으니 유의하세요. 11/1 BOJ 16132 - 그룹 나누기 (Subset) Gold 4 #knapsack 각 부분집합의 합은 $\frac{N(N+1)}{4}$가 되어야 한다. 이 값이 정수가 아니면 답은 $0$이다. 그렇지 않으면, $1, 2, \cdots, N$으로 $\frac{N(N+1)}{4}$를 만드는 경우의 수를 knapsack dp로 세어주자. BOJ 11657 - 타임머신 Gold 4 #bellman_ford 음수 가중치가 있는 그래프에서 최단 경로를 구해야 하므로 벨만-포드를 써주자. 벨만-포드 알고리즘의 기초 문제이다. BOJ 11404 - 플로이드 Gold 4 #floyd-warshall 모든 정점 사이의 최단 경로를 ..

10/21 ~ 10/31에 푼 문제들입니다. 문제의 풀이에 대한 스포일러가 포함되어 있습니다. 잘못된 풀이가 있다면 지적해주세요. 10/21 BOJ 9741 - Interior Lattice Points Gold 3 더보기 #pick's_theorem #polygon_area 픽의 정리란? 2차원 격자 위의 단순 다각형에 대하여, 다각형의 넓이를 $a$, 다각형의 변 위에 존재하는 정수 좌표 점의 수를 $b$, 다각형의 내부(경계 미포함)에 존재하는 정수 좌표 점의 수를 $i$라고 하면 $A = i + \dfrac{b}{2} - 1$가 성립한다. 이 식을 $i$에 대해 정리해서 풀자. 세 점이 일직선상에 있는 경우를 조심하자. 10/22 BOJ 25187 - 고인물이 싫어요 Gold 4 더보기 #dfs ..

Codeforces Round 906 (Div. 2) CP를 연습하고 싶어 시간만 된다면 앞으로 많이 해볼 계획이다. A - Doremy's Paint 3 00:06 AC 홀수 항과 짝수 항이 모두 같을 수 있는지 판별하면 된다. B - Qingshan Loves Strings 00:15 AC $s$가 good이면 무조건 Yes이다. $s$와 $t$가 good이 아니면 무조건 No이다. 그렇지 않은 나머지 경우에 대해서만 생각하면, $t$는 항상 good이다. $s$가 good이 되지 못하도록 하는 모든 쌍에 대해, 그 쌍에 $t$를 넣었을 때 해당 쌍이 good에 기여할 수 있는지 판별하면 된다. C - Qingshan Loves Strings 2 00:48 AC $i = 1$부터 차례대로, $s_i ..

Codeforces Round 900 (Div. 3) 생애 두 번째 코드포스 대회이다. 첫 번째는 글을 쓰기엔 몇 달 지나기도 했고, 너무 말아먹어서 pass CP가 다 그렇듯, 알고리즘 분류와 난이도를 볼 수 없고 영어로 되어있어서 실력 향상에 많이 도움이 될 것 같아서 시작했다. 열심히 해서 힘이 닿는 데까지 점수를 올려보려 한다. A - How Much Does Daytona Cost? 00:04 AC $k$가 등장했다면, 그 자체로 $k$가 most common element인 subsegment가 될 수 있다. B - Aleska and Stack 00:23 AC $a_1 = 2, a_2 = 3$으로 놓고 $i>2$인 $i$에 대해 $a_i$를 $a_{i-1}$보다 크면서 $3(p-a_{i-1}..