PS 일지

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

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

10/11 ~ 10/20에 푼 문제들입니다.문제의 풀이에 대한 스포일러가 포함되어 있습니다.잘못된 풀이가 있다면 지적해주세요.10/11BOJ 10436 - 무한 유리수 트리Gold 4더보기#math #tree$pq$인 경우는 $p BOJ 23734 - Miswritten DFSPlatinum 5더보기#dp_tree #dfs #recursion정점 $n$의 왼쪽 자식과 오른쪽 자식을 각각 $l, r$이라고 하자. $n$을 루트로 갖는 dfs를 실행할 경우 $n$의 서브트리의 정점 수만큼의 탐색이 진행된다. 이 때, $l$을 루트로 하는 dfs는 두 번 수행되므로 서브트리의 수 $sub[n] = 2sub[l] + sub[r] + 1$로 정의하자. 이는 한 번의 dfs로 쉽게 구할 수 있다. 이제 ..

10/1 ~ 10/10에 푼 문제들입니다.문제의 풀이에 대한 스포일러가 포함되어 있습니다.잘못된 풀이가 있다면 지적해주세요.10/2BOJ 30284 - KarjerasGold 5더보기#prefix_sumimos법으로 알려져있는 걸로 알고 있다. 구간의 변화를 시작점과 끝점에 각각 +1, -1을 취하는 방법인데, 이 문제에선 반대로 -1, +1을 해주면 된다. BOJ 30276 - TraukinysGold 4더보기#greedy만약 $a_{i}$가 $K$보다 작다면, 무조건 가까운 곳에서 끌어오는 것이 이득이다. 끌어오는 쪽의 $a_{i}$가 $K$보다 작아도 무조건 끌고 오는 것이 포인트이다. 아이디어는 금방 떠올랐지만 개인적으로 구현이 힘들었다.10/3BOJ 6611 - Simon the SpiderPl..

9/21 ~ 9/30에 푼 문제들입니다.문제의 풀이에 대한 스포일러가 포함되어 있습니다.잘못된 풀이가 있다면 지적해주세요.9/21BOJ 30092 - 슥삭슥삭 나무자르기Platinum 1더보기#tree #lca경로 $a$-$b$와 $c$-$d$가 두 점 이상을 공유하는 지 판별하자. 여러 lca를 구해서 경우를 따져보면 된다. BOJ 30155 - Crazy Malvika discovers Crazy Fibonacci functionSilver 3더보기#math주어진 수열은 첫 6개의 항이 계속 반복되는 형태이다. 9/23백준에 올라온 ZOAC 대회 문제들을 풀었다. 처음으로 대회 문제 출제진으로 참여했다. 문제 만들기도 어려웠지만, 다른 사람들이 만든 문제를 풀고 검수하는 게 훨씬 힘들었다. BOJ..