jay153의 PS 일지

https://codeforces.com/contest/2104 Performance Rating : 2250 A$a$, $b$, $c$ 중 $b>\frac{a+b+c}{3}$이거나 $a+b+c\;\mathrm{mod}\; 3\neq 0$이면 불가능하다. B마지막 $k-1$개는 무조건 들어갈 수밖에 없으므로 뒤에 $k-1$개의 원소의 합과 multiset을 활용해 나머지 숫자 중 최댓값을 더해 답을 구했다. C$1$이 쓰인 카드와 $n$이 쓰인 카드를 모두 가지게 되면 다른 카드와 관계없이 이긴다는 것을 관찰했다. $1$과 $n$이 같은 사람에게 있으면 둘 다 가지고 있는 사람을 출력했다. 그 후 $0$을 Bob이 가지고 있다면 $n-1$을 Bob이 가지고 있으면 $n$은 $0$으로, 나머지는 $n-1..

https://codeforces.com/contest/2098 Performance Rating : 2300 A우선 당연히 한 날짜에 베팅이 4개 이상이면 성립한다는 것을 생각했다. 그 후 같은 날짜로 2개가 있으면 $a_i+1$이나 $a_i+2$ 중 하나를 확정할 수 있다는 것을 관찰했고 이를 통해 앞에서부터 원소를 하나씩 확정해 나가면서 적어도 하나를 맞추도록 베팅이 가능한지 판단했다. B처음부터 접근을 잘못했다. $dp$로 카운팅을 하면 되는 문제로 파악하여 풀었는데 틀렸다. 틀린 이후 반례를 찾은 뒤 풀이를 고쳐보려 하였으나 도저히 고칠 엄두가 안나 C로 넘어갔다. 업솔빙을 해보니 그래프 모델링을 해서 경우의 수를 카운팅 하는 문제였다. C$(x, y)$를 지나고 기울기가 $frac{v_x}{..

https://codeforces.com/contest/1956 Performance Rating : 2950 A문제의 설명이 길어서 문제를 이해하는데 시간이 오래걸렸다. 해석을 해보니 답은 $\mathrm{min}(a_1 - 1, n_i)$를 출력하면 되는 문제였다. B2개 존재하는 숫자의 개수가 정답이다. C가장 이상적인 해의 형태를 먼저 생각해 보았다. 예제에서도 볼 수 있듯이 $1$이 1개, $2$가 3개, $\cdots$, $n$이 $2n-1$개 존재하는 것이 최적일 것 같았는데 이를 만들 수 있는지를 생각해 보다가 $2i$번쨰 실행에서는 $i$번째 행을 $n, \cdots,1$로 만들고 $2i+1$번째 실행에서는 $i$번째 열을 $n, \cdots,1$로 만들면 예상한 최적의 해가 나온다는 ..

https://codeforces.com/contest/2096 Performance Rating : 2400 A''의 의미를 잘못 파악하고 문제를 풀었다가 틀린 것을 확인하고 다시 풀어 9분이라는 많은 시간이 들어갔다. 문제를 잘 읽자. B생각보다 헷갈려서 고민을 하다가 $\mathrm{max}(a_i,b_i)$는 모두 더하고 $\mathrm{min}(a_i,b_i)$ 중 가장 큰 $k$개를 더하면 된다는 것을 알게 되었다. C처음에 하나의 행 또는 열에 여러 번 공사가 가능한 것으로 착각해 고민을 하다가 문제를 잘못 읽었음을 알게 되었다. 그 후에는 특정 행에서 수행하는 것은 열끼리 비교에서 영향을 주지 않는다는 것을 바탕으로 $dp$를 활용해 풀었다. 행과 열에 대해 $dp[i+1][j]$를 이전..

https://codeforces.com/contest/2093 Performance Rating : - A$n$이 홀수일 때 YES, 짝수일 때 NO이다. B가장 뒤에 있는 숫자 하나와 그 앞에 있는 $0$들 빼고는 모두 지워야 한다. C$k>1$일 경우 $n=1$, $k=2$인 경우를 제외하면 모두 합성수이고, 나머지는 소수 판정을 해주면 된다는 생각으로 답을 제출했고 당연히 맞은 줄 알았다가 나중에 보니 틀린 것을 확인했는데 $n=1$, $k=1$인 경우 예외 처리를 해주지 않은 것이었다. D재귀적인 성질을 가지고 있으므로 재귀 함수로 풀 생각을 했다. 케이스를 나누는 경우가 생각보다 많아 헷갈리는 바람에 구현에 시간을 조금 쓰게 되었다. E문제를 보자 마자 경계점을 기준으로 되는 구간과 안되는..

https://codeforces.com/contest/2084 Performance Rating : 2500 A$n$이 짝수일 때에는 $-1$, $n$이 홀수일 때에는 $n,1,\cdots,n-1$을 출력하는 코드를 작성하였다. $n$이 짝수일 때 안 되는 이유를 증명하지는 않고 proof by AC로 했다. B우선 $\mathrm{gcd}(a_{i+1},\cdots,a_n)$는 $\mathrm{min}(a_{i+1},\cdots,a_n)$이하이므로 $a_i$ 중 최솟값은 좌변에 들어가야 한다는 생각을 했다. 그러면 $a_i$ 중 최솟값을 구해놓고 나머지 중 구한 최솟값의 배수인 것들은 모두 우변에 넣는 것이 최선이므로 최솟값의 배수인 숫자들의 최대공약수를 구해 최솟값과 일치하는지를 확인하여 답을 ..

https://codeforces.com/contest/1957 Performance Rating : 2350 A$a_i$를 입력받으면서 개수를 저장해 두고 저장된 개수에 3을 나눠서 더하는 문제였다. B$k$를 이진수로 나타냈을 때 $x$자리수라고 했을 때 1이 $x$개라면 $k$ 하나만 출력하면 되고 $x$개보다 작다면 $2^x-1$, $k-x$, x$, 나머지를 $0$으로 채우면 되는데 이는 $1$의 개수가 $x$개일 때에도 적용할 수 있어 $n$이 1일 때에만 예외처리를 해주고 구현했다. C최종 상태는 하나의 행에 하나씩의 룩이 배치된다. 또한 지금까지 결정된 열이 $p$개라고 하면 $(n-p)\times (n-p)$ 판에 룩을 채우는 경우의 수와 같다. 각 경우에 대해 $p$를 구해주고 $i..

https://codeforces.com/contest/2086 Performance Rating : 2850 A$n$을 입력받고 $2n$을 출력하는 문제였다. B$r$은 $nk$에 고정해 두고 가능한 $l$의 최댓값을 구하면 된다. 반복이 된다는 점을 활용하여 $b_l+\cdots+b_{nk}\geq x$인 $l$의 최댓값을 구했다. C관찰을 하다가 특정 숫자를 고치기 시작하면 순열 사이클 분할을 해놓은 모든 숫자들을 다 고쳐야 한다는 것을 알게 되었다. 쿼리별로 입력을 받은 뒤 이미 끝난 숫자라면 답을 출력하고 아니라면 순열 사이클을 찾아 개수를 답에 더해주었다. D홀수 인덱스를 가진 부분과 짝수 인덱스를 가진 부분이 정확히 분리되어 있다는 생각을 했다. 우선 알파벳들의 분배를 적절히 잘했을 경우 ..

https://codeforces.com/contest/1967 Performance Rating : 2400 A$k$를 적절히 분배해서 $a_i$의 최솟값을 크게 만들고 최솟값의 개수를 줄이는 것이 좋은 전략인 것을 눈치채고 적절히 분배하는 방법으로는 파라메트릭 서치가 적절해 보여서 이를 구현했다. B1$\frac{a+b}{b\cdot \mathrm{gcd}(a,b)}$가 정수이기 위해서는 $\frac{a+b}{b}$가 정수여야 하므로 $a$가 $b$의 배수인 것을 생각했다. $a=kb$라고 했을 때 $\mathrm{gcd}(a, b)=b$이므로 $\frac{k+1}{b}$가 정수여야 하는데 이때 $b$를 고정하면 $k+1=pb$이라는 사실을 알 수 있고 $a=(pb-1)b$가 되므로 $a$를 $b^2..

https://codeforces.com/contest/1973  Performance Rating : 2150 A3개의 수의 합이 홀수라면 불가능하고, 짝수라면 $\mathrm{min}(sum/2,p_1+p_2)$를 출력했다. B$a_i|\cdots|a_j=(a_i|\cdots|a_{j-1})|(a_{i+1}|\cdots|a_j)$라는 점을 활용하면 $k$에서 성립한다면 $k+1$에서는 성립할 것이므로 파라메트릭 서치를 사용할 생각을 했다가 한 번의 판단에 $O(n^2)$의 시간이 드는 것을 확인하고 다른 방법을 찾기 시작했다. 비트연산이므로 비트별로 보면 되지 않을까 생각하던 중 각 자리의 비트별로 $1$인 수가 하나라도 있으면 연속한 $0$의 최장길이+1 만큼의 길이가 필요하다는 것을 관찰하여 풀었..