jay153의 PS 일지

https://atcoder.jp/contests/arc195  Performance Rating : 2154 A바로 생각이 안나서 당황했으나 2개 이상인지 판별만 하면 된다는 것에 주목했다. 앞에서부터 매칭하고 뒤에서부터 매칭한 것이 다르면 2개 이상인 것이기 때문에 2번의 매칭을 비교하여 풀었다. B-1은 자유롭게 바뀔 수 있기 때문에 -1의 개수는 따로 세주고 -1이 아닌 숫자들의 합으로 최대한 같은 숫자를 많이 만드는 풀이를 생각했다. $A$의 각 숫자의 개수를 세주는 map과 $B$의 각 숫자를 세주는 map을 따로 만들어둔 뒤 map 2개를 모두 순회하면서 합으로 만들 수 있는 숫자의 개수를 또 다른 map에 저장해두었다. $A$와 $B$에 있는 숫자 중 최댓값보다는 합이 커야하기 때문에 그 ..

https://atcoder.jp/contests/abc398  Performance Rating : 1684 A$N$이 홀수일 때와 짝수일 때 나누어 출력해 주었다. B각 숫자의 개수를 세준 뒤 정렬하고 가장 큰 수가 3 이상, 두 번째로 큰 수가 2 이상인지 확인하였다. C각 숫자의 개수를 map으로 세준 뒤 다시 한번 순회하면서 개수가 하나인 수 중 가장 큰 수의 인덱스를 출력하면 되는데, 가장 큰 인덱스를 출력하는 것인 줄 알고 WA를 한번 받았다. D연기의 좌표를 옮기는 것보다 기준점의 좌표를 옮기는 것이 낫겠다는 생각을 했다. map에 $(0,0)$의 기준점 기준 위치를 1로 바꿔주고 $mp[(x+r, y+c)]$를 출력해 주는 방식으로 해결했다. E짝수 사이클을 만들면 안 되는 것으로 문제를..

https://atcoder.jp/contests/abc397   Performance Rating : 2335 A기본적인 대소관계 비교 문제였다. B$i$번째와 $(i+1)$번째 사이에 문자를 삽입하면 $1$부터 $i$번째까지 문자의 위치에는 영향을 주지 않기 때문에 앞에서부터 채워 나가야겠다는 생각으로 풀었다. C가장 처음 생각난 풀이는 레이지 세그먼트 트리였으나 조금 더 생각을 해보니 각 숫자의 개수를 세어두면 $A_1$부터 차례로 보면서 왼쪽과 오른쪽에 있는 숫자 종류의 개수를 $O(1)$의 시간에 구할 수 있다. D처음에는 풀이가 떠오르지 않았다. 투 포인터로 $x$, $y$를 찾아나가는 풀이가 가능한지 생각하기 위해 가능한 $x$의 범위를 생각해 보기로 했다. $(x+1)^3-x^3=3x^2+..

https://atcoder.jp/contests/arc194   Performance Rating : 1900 A수열에서 연속한 2개의 항을 함께 제거할 수 있고 제거한 뒤 수열의 합을 최대로 만드는 문제인데 $dp[i]$를 $A_1$,$\cdots$,$A_i$까지의 숫자들로 만들 수 있는 합의 최댓값이라고 정의하면 $dp[i]=\mathrm{max}(dp[i-1]+A_i,dp[i-2])$라는 식을 세울 수 있다. B가장 큰 원소를 뒤로 보내는 방식으로 버블정렬을 할 때가 최선이라고 생각했다. $x$가 $x$번째로 가기 위해서는 자신보다 뒤에 있는 $x$보다 작은 수들을 앞으로 보내야 하는데 이를 최대한 앞에서 하려면 자신보다 큰 수들을 모두 제자리에 놓고 해야하기 때문이다. 이렇게 정성적으로 생각한 ..

https://atcoder.jp/contests/abc396  Performance Rating : 1616 A$v[i-1]=v[i]=v[i+1]$인 $i$가 존재하는지 찾는 문제였다. B평범한 스택 문제였다. C어떤 색깔의 공을 고르던 있는 공 중 가장 큰 것을 뽑는 것이 이득이고 흰 공의 경우에는 검은 공 개수 이하로 고를 때 최댓값을 찾아주어야 한다. 그러므로 정렬과 누적합, 누적 최댓값을 활용하여 답을 구했다. D$N\leq 10$이라는 점에 주목했다. $O(N!)$이 충분히 돌아가는 작은 수이기 때문에 모든 경로를 다 살펴볼 생각을 했다. $1$부터 $N$까지의 수가 모두 있는 $N!$개의 순열을 생각하자. 각 순열에서 $1$과 $N$사이에 있는 숫자들을 순서대로 방문한다고 생각하면 모든 경로..

https://atcoder.jp/contests/abc395  Performance Rating : 1960 A단조증가수열인지 판단하는 단순한 문제였다. B바깥에서부터 '#', '.'을 번갈아가면서 찍어주면 되는데 구현 과정에서 시간이 꽤 걸렸다. C$10^6+1$크기의 배열에 각 숫자가 나온 최근 인덱스를 저장해 두면 되는데, 답을 출력하는 것에 삼항 연산자를 잘못 사용했다가 디버깅하느라 시간이 조금 소요됐다. D배열 3개를 활용해서 풀면 되겠다는 생각을 했다. 둥지의 새들을 서로 바꿀 때 새들의 둥지 번호를 직접 바꾸면 시간 초가가 날 것이 분명하기 때문에 $nest$를 정의해서 $nest$의 값을 swap 해주면 $nest[v[i]]$로 새의 둥지 번호를 알 수 있기 때문에 $nest$를 활용해 ..

https://atcoder.jp/contests/arc193   Performance Rating : 1400 AA와 B 모두 처음에 풀이가 떠오르지 않았는데 A 솔브수가 올라가는 속도를 보고 A를 먼저 풀었다. 이 문제는 $[L_i,R_i]$에서 겹치지 않는 구간을 활용하여 $[L_j,R_j]$에 도달하는 문제인데, 도달하는 과정에서 최소한의 $w$를 사용해야 한다. $L_i\leq L_j$라고 하자.  $[L_i,R_i]$와 $[L_j,R_j]$가 겹치지 않으면 바로 이동하는 것이 최선이고 중간에 3개 이상의 구간을 거치는 경우 하나를 제외시키고도 충분히 도달 가능하다는 것을 깨달았다. $R_p\mathrm{max}(R_i,R_j)$인 경우 $p$번 노드 하나만 거치고도 도달할 수 있고 $R_iR_..