jay153의 PS 일지

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 만큼의 길이가 필요하다는 것을 관찰하여 풀었..

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://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://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$을 없애준 ..