jay153의 PS 일지

https://codeforces.com/contest/2092  Performance Rating : 2400 A유클리드 호제법에서 $gcd(a, b)$의 최댓값은 $|a-b|$이므로 $a_i$에서 최댓값과 최솟값의 차이가 답이라는 생각으로 풀었다. B문제를 잘못 읽고 $a$와 $b$를 같게 만들 수 있는지를 출력해서 틀렸다. 결국 서로 바꿀 수 있는 위치들이 정해져 있으므로 $a_{2i}$, $b_{2j+1}$에서 $0$의 개수와 $a_{2i+1}$, $b_{2j}$에서 $0$의 개수를 각각 세어 두고 각각의 개수가 $n/2$, $(n+1)/2$이상인지 확인했다. C모든 숫자가 짝수 또는 홀수라면 시행을 할 수 없으므로 최댓값을 출력했다. 이제 짝수와 홀수가 각각 하나 이상씩 존재하는 경우에 대해 생..

https://codeforces.com/contest/1975  Performance Rating : 2450 A한 번의 수행밖에 못하므로 $a_i>a_{i+1}$인 $i$의 개수를 세고 0개라면 "Yes", 2개 이상이라면 "No", 1개라면 $a_1$과 $a_n$의 크기를 비교하였다. B가장 작은 수는 다른 수의 어떤 수의 배수일 수 없기 때문에 정렬을 해두고 처음부터 수를 보면서 $a_0$의 배수인지 확인하고 배수가 아니라면 $a_i$를 저장해두고 나머지 수들이 두 수중 하나의 배수인지 확인하였다. 구현 과정에서 $a[i]$라고 써야 하는 것을 $x$를 쓰는 실수를 하여 WA를 한 번 받았다. C처음에 순서를 바꿀 수 있는 것인줄 알고 두 번째로 큰 수를 출력했다가 틀렸다. 생각을 해보다가 그러면..

https://codeforces.com/contest/1977Performance Rating : 1700 A$m>n$이거나 $n$과 $m$의 기우성이 다르면 "No"이다. B어차피 모든 숫자를 만들 수 있다는 것이 보장된다는 조건이 있으므로 $a_0,\cdots,a_i$까지의 숫자들로 만들 수 있는 최댓값을 저장해 두고 이를 바탕으로 큰 인덱스부터 결정을 해주며 풀었다. C$n$개의 수의 최소공배수가 $n$개의 수 중 최댓값과 같을 때 잘 처리해주어야 하겠다는 생각은 빨리 했으나 그 경우에 몇 개의 숫자를 골랐을 때 가능한 최소공배수가 최댓값의 약수밖에 없다는 것을 눈치채지 못하고 틀렸다. D어차피 각 열을 1이 하나만 존재하도록 만들 수 있는 문자열은 각 열마다 $n$개씩 밖에 없다는 것을 보고 생..

https://codeforces.com/contest/1981  Performance Rating : 2450 A어차피 $2$로 나누는 것이 이득이기 때문에 $l$ 이상, $r$ 이하인 $2^n$ 중 가장 큰 수를 찾으면 되는데, 문제를 처음 보고 약수가 가장 많은 수를 찾는 것으로 착각하고 시간 손해를 조금 봤다. B결국 $low=\mathrm{max}(0, n-m)$, $hi=n+m$ 사이의 수를 모두 bitwise or 했을 때 값을 구하는 문제였다. $low$와 $hi$에서 처음으로 비트가 달라지면 그 아래의 비트들은 모두 1로 만들어진다는 것을 깨닫고 구현했다. C두 수의 가장 큰 비트를 맞춘 뒤 두 수가 같아질 때까지 2로 나누는 과정을 거쳐야 두 수 사이의 변환이 가능하다는 것을 생각했다...

https://codeforces.com/contest/1979 Performance Rating : 2600 A$\mathrm{min}( \mathrm{max}(a_1,a_2),\cdots, \mathrm{max}(a_{n-1},a_n))-1$을 출력했다. B예제를 보고 $|n-m|$의 최소 비트에 해당하는 숫자를 출력하는 것 같았고 proof by AC를 했다. C결국 어떤 수가 걸리더라도 비슷한 금액을 받아야 낭비가 없다는 생각을 했다. $1$부터 $n$까지 어떤 수가 걸리더라도 $1$부터 $20$까지의 최소공배수인 232792560만큼을 돌려받게 설정한 뒤 베팅 금액의 통합이 232792560보다 작은지 확인했다. D예제를 바탕으로 관찰을 한 뒤 casework를 했다. 결국 모두 $k$개씩 연속..

https://codeforces.com/contest/2089  Performance Rating : 2500 A예제에서 모두 2부터 나오길래 2부터 순차적으로 소수들이 최대한 많이 나오는 방법으로 배치하는 것을 고려해봤으나 $n$이 커질수록 $n/3-1$개보다 적은 개수가 나올 것 같다는 생각이 들었고 다른 방법을 찾기 시작했다. 특정 $p$에서 시작하여 $p, p-1, p+1, \cdots$ 이런식으로 배치하면 $c_i$를 $p$로 유지시킬 수 있다는 것을 알게 되었고 $n=1$인 경우에만 예외처리를 해준 뒤 $n/2$와 가장 가까운 $p$에서 시작하여 $p-x$, $p+x$를 계속 출력해주는 풀이를 작성했다. B1처음에는 $b_i$가 줄어들지 않는 것으로 생각하고 풀이를 짰다가 $b_i$도 줄어든..

https://codeforces.com/contest/2085 Performance Rating : 3000 A모두 같은 문자로 이루어진 것이 아니라면 한 번만 바꿔서 조건을 만족할 수 있다는 것을 관찰하면서 시작했다. $k=0$인 경우에는 $s$랑 $rev(s)$를 비교하여 답을 출력했고 $k\geq 1$인 경우에는 모든 문자가 같으면 "No", 아니면 "Yes"를 출력했다. B$0$이 없으면 $1\;n$ 한 번만 해줘도 된다는 것을 관찰하였고, $0$이 하나 있다면 한 번의 수행으로 $0$을 없애준 뒤 한 번의 수행으로 끝내줄 생각을 했다. $0$이 2개 이상일 경우 수열을 $0$이 양 끝에 있다면 수열을 두 부분으로 나누고 아니라면 $0$이 없는 부분을 제외하고 수행을 한번 하여 $0$을 없애준 ..

https://codeforces.com/contest/1978 Performance Rating : 2750 A$a_1,\cdots, a_{n-1}$중의 최댓값과 $a_n$을 더하여 출력하는 문제였다. B$a>b$, $a C$n$이 홀수일 때와 짝수일 때 Menhattan value의 최댓값을 계산해보았다. $n=2k$이면 $2k^2$, $n=2k+1$이면 $2k(k+1)$이 최대였다. $k$가 홀수이거나 최댓값보다 크면 "No"를 출력해주었다. 나머지 경우에 대해서는 처음에 $a_i=i$로 설정해두고 $k$가 $0$이 될 때까지 양 끝의 숫자를 바꾸는 것을 반복해주면 되겠다는 생각을 했다. 그러나 WA를 받았고 오버플로우가 문제일 것이라고 생각해 $n$의 자료형을 $ll$으로 바꿨으나 또 WA가 나와..

https://codeforces.com/contest/1982  Performance Rating : 2400 A$(x_1, y_1)$가 $(x_2,y_2)$로 바뀌면서 $x=y$가 되는 순간이 존재하는지 판단하는 문제였다. 사잇값 정리를 생각하면서 $x_1>y_1$, $x_2y_2$가 성립하면 "NO", 아니면 "YES"를 출력했다. B$k$의 상한이 $10^9$이라서 고민을 시작했다. 5분정도 고민을 해보니 $x$가 $1$이 될 때까지 $y$를 나누는 횟수는 $logx$로 바운드 될 것 같았고 $x$를 $y$로 나눈 나머지로 $x$가 $y$의 배수가 될 때까지 시행을 얼마나 해야 하는지도 구할 수 있기 때문에 이를 바탕으로 시뮬레이션을 돌렸다. Cdp문제일 것 같다는 감이 왔다. $dp[i]$를 $..

https://codeforces.com/contest/1983 Performance Rating : 2550 A$a_i=i$로 설정하면 조건을 만족한다는 것을 생각하고 출력했다. B처음에 문제를 보고 당황을 했다. 5분정도 생각을 하다가 실행을 하는 것이 각 행과 열의 합의 3으로 나눈 나머지를 바꾸지 못한다는 것을 알게 되었고 각 행과 열의 합을 3으로 나눈 나머지가 하나라도 다르면 "NO"라는 것을 알게 되었다. 3으로 나눈 나머지가 같을 때 왜 모두 변환이 가능한지는 증명하지 않고 "YES"를 출력하는 코드를 제출했는데 맞았다.  C일단 수열의 모든 인덱스를 다 사용하는 것이 손해될 것은 없다는 관찰로 문제를 풀기 시작했다. 처음과 중간, 끝을 $a$, $b$, $c$를 어떤 순서로 사용할지에 따..