jay153의 PS 일지

https://www.acmicpc.net/problem/18976  코드http://boj.kr/97c257d8f1b74482be14bb8980f3227c Petrozavodsk Programming Camp Summer 2018 Day 3: MIPT Contest K 난이도 : P2 Elapse Time : 15min 문제를 보고 단순화를 해야겠다는 생각이 들었다. 결국 문제를 요약하면 점과 선분들에 의해 몇 개로 나누어져 있는 평면에서 최소비용의 선분을 제거하여 평면이 분리되어 있지 않도록 만들라는 것이었다. 처음에는 분리되어 있는 평면들에 각각 번호를 붙여준 뒤 비용 순으로 선분들을 정렬하고 선분을 기준으로 양쪽에 있는 평면이 같은 평면인지 확인하는 것을 Dsu를 활용해 처리해 줄 생각이었다. 평..

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://www.acmicpc.net/problem/23176  코드http://boj.kr/7d3b2e772d524996bab2a9994f076fe5 2021 KAIST 11th ICPC Mock Competition G 난이도 : D5 Elapse Time : 80min 체력의 상한이 존재하지 않는다면 $i$번째 과정이 끝난 뒤 남은 체력은 $x+a_1+\cdots+a_i$이다. 남은 체력이 누적합과 연관되어 있긴 한데 상한이 존재한다는 것이 문제였다. 체력이 변하는 과정에서 언제 체력이 최솟값이 될지를 생각해 보니 구간합이 최소인 구간의 끝일 것 같다는 느낌이 왔다. 구간합이 최소인 구간을 $[s, e]$라고 하면 $s\leq i\leq e$인 $i$에 대해 $a_s+\cdots+a_i\leq..

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://codeforces.com/contest/1965  Performance Rating : 2000 A가장 작은 값이 1인지 아닌지가 중요해보였다. 가장 작은 수가 1인 경우 선택권이 없지만 1보다 큰 경우는 선택권이 생기기 때문이다. 가장 작은 값이 $x$이고 $x>1$이면 $(x-1)$개 또는 $x$개를 가져감으로써 같은 상황에서 먼저 할 것인지 나중에 할 것인지를 선택할 수 있기 때문에 무조건 이길 것이라고 생각했다. 그러므로 가장 작은 값이 1보다 큰 상황이 먼저 오는 사람이 이길 것이라는 생각이 들었고 가장 작은 값이 계속 1이라면 $n$의 홀짝성에 따라 승패가 결정될 것이라고 생각했다. 하지만 중복된 숫자가 존재하면 이는 한 묶음으로 봐도 되는데 이를 처리하는 과정에서 실수를 하여..

https://www.acmicpc.net/problem/8415  코드http://boj.kr/a2cc1f96953c4eb1accf307a94c67719  Algorithmic Engagements PA 2006 7-5 난이도 : P1 Elapse Time : 실패 문제를 보고 이분 매칭의 개수가 $N$개가 될 수 있으면 룩을 놓을 방법이 존재한다는 것이므로 이분 매칭을 하는 것으로 문제를 풀기 시작했다. 매칭을 해놓고 변경할 수 있는 경우의 수를 dp등의 방법을 활용해 세어보는 풀이를 생각해 보았는데 풀이가 생각나지 않았고 다른 풀이를 찾지 못했다. 시간을 두고 생각하다가 정사각 행렬의 determinant를 생각해보게 되었는데 홀짝성만 판단하면 되는 이 문제와 큰 관련이 있을 것 같다는 생각이 들었..

https://codeforces.com/contest/1995  Performance Rating : 2250 A$n^2$개의 점이 $n$개짜리 그룹 하나, $1,\cdots,(n-1)$개짜리 그룹 각각 2개씩으로 나누어지므로 최대한 큰 그룹으로 사용해 주는 것이 이득인데, 구현과정에서 시간이 조금 걸렸다. B1map에 나온 숫자들의 개수를 저장해 두고 map을 순회하면서 $x$, $x+1$의 개수를 바탕으로 답을 구할 생각이었다. 답이 $m$을 초과하면 안 되므로 $x$짜리를 몇 개 선택하는지에 따라 최댓값을 모두 계산하여 그중 최댓값을 답으로 출력했다. B2B1에서 쓴 풀이를 그대로 쓸 수 없었다. 각각의 개수가 $10^9$개까지 나오기 때문이었는데, 고를 수 있는 숫자가 $x$, $x+1$뿐이라는..

https://www.acmicpc.net/problem/14734 코드http://boj.kr/d53a0455fbfd4d92b9ef11c779e84844 2017 KAIST 7th ACM-ICPC Mock Competition A 난이도 : P1 Elapse Time : 100min 예제를 보고 왼쪽 $(N-1)$줄을 세로로 맞추어 주고, 오른쪽 $(N-1)$줄을 세로로 맞춘 뒤 가운데 두 줄을 세로로 배열하는 풀이를 생각했다. 왼쪽 $(N-1)$줄은 왼쪽부터, 오른쪽 $(N-1)$줄은 오른쪽부터 한 줄씩 세로로 바꾸도록 코드를 짰는데 WA를 받았다. 케이스 고려를 많이 빼먹은 탓이었다. 한 줄을 모두 세로로 바꿨을 때 'U'가 위치해야 하는 부분에 'L' 또는 'R'이 위치하면 다시 'L' 또는 'R..

https://codeforces.com/contest/1993  Performance Rating : 2800 A주어진 $s$에서 'A', 'B', 'C', 'D'의 개수를 각각 세놓고 개수와 $n$중 최솟값을 더해주면 된다. B홀수가 존재하면 모두 홀수로 만들어야 한다는 것은 빠르게 알아차려서 짝수만 있으면 0을 출력해 주고 아니면 짝수의 개수를 출력하는 코드를 짰으나 예제가 안 나와서 다시 보니 작은 것에 더해준다는 것을 발견했다. 그래서 $a$를 정렬해 놓고 현재까지 만들어진 가장 큰 홀수보다 짝수이면서 더 큰 값이 나오면 답을 1 키워주는 코드를 짰지만 틀렸다. 틀리고 다시 생각해 보니 2번을 실행하는 것은 가장 큰 짝수에서 하면 나머지 짝수들은 모두 한 번에 합칠 수 있다는 것을 알게 되어 고..

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