jay153의 PS 일지

https://codeforces.com/contest/1988 Performance Rating : 2450 A예제를 보고 규칙성을 찾지 못해 문제를 읽었다. 결국 1개의 $n$을 한 시행마다 $k-1$개의 $1$을 만드는 형식으로 진행하는 것이 최선이므로 $(n+k-3)/(k-1)$을 출력했다. B0이 여러개 연결되어 있으면 하나의 0으로 바꾸는 것이 가능하고 1을 포함하여 수행하면 (1의 개수)-(0의 개수)의 값이 계속해서 줄어드는 구조라는 것을 관찰했다. 그러므로 1의 개수는 그냥 세주고 0의 개수는 연속한 것은 1개로 세준 뒤 1의 개수가 크면 "Yes", 아니면 "No"를 출력했다. C1인 비트의 개수가 중요해 보였다. 결국 최상위 비트가 0인 것은 하나 밖에 못 나오기 때문에 최상위 비트..

https://codeforces.com/contest/1994  Performance Rating : 2300 A1부터 $nm$까지의 수를 모두 다르게 만들어야 하므로 $n=1$, $m=1$인 경우 안된다는 예외 처리를 해주고 $a_{i,j}=a_{i,j}%(nm)+1$을 해주면 모두 다른 숫자로 바꿀 수 있다. B문자열에서 1이 나오기 시작하는 위치부터는 모든 자리를 원하는대로 바꿀 수 있다는 생각을 했다. 그러므로 $t$에서 1이 먼저 나오기 시작한 경우에는 "NO"를 출력해주면 된다. $s$에서 1이 먼저 나오기 시작했을 때를 생각해보아야 하는데, 1이 나오기 전까지 0을 1로는 못바꾸지만 1은 자유롭게 0으로 바꿀 수 있으므로 나머지의 경우는 모두 "YES"일 것이라고 생각했다. C풀이가 바로 ..

https://codeforces.com/contest/1990   Performance Rating : 2300 A생각보다 풀이가 바로 생각나지는 않았다. 가장 큰 숫자가 홀수개라면 첫 턴인 사람이 이긴다는 것으로 생각을 시작했다. 가장 큰 숫자가 짝수개라면 두 번째 큰 수가 홀수개인지 보면 되는데 이 생각을 이어나가다 보니 홀수개인 숫자가 하나라도 있으면 첫 턴인 사람이 이긴다는 결론이 나왔다. B경우의 수가 많다는 것, 그리고 B번 문제라는 것을 생각하여 어느 정도 정형화 된 풀이가 존재할 것이라고 예상했다. $y C모든 숫자가 0이 될 때까지 시뮬레이션을 할 수는 없으므로 우선 관찰을 시작했다. 한 번 실행하고 나서부터는 $a$가 오름차순이 되므로 규칙을 파악할 수 있을 것 같았다. 우선 한 번 ..

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

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

https://codeforces.com/contest/2071  Performance Rating : 2300 A예제를 보고 규칙성을 못 찾아서 문제를 읽어보니 세 명이라길래 3으로 나눈 나머지를 봤더니 1인 경우 YES, 0, 2인 경우 NO였다. B처음에는 2 1 3 4 ... 이렇게 출력해 주면 끝나는 문제인 줄 알고 제출했다가 틀렸다. $n(n+1)/2=k^2$인 $n$이 1밖에 없는 줄 알았는데 더 있는 것을 확인하고 $n(n+1)/2=k^2$인 $n$에서는 -1을 출력하고 아니라면 $n$이하이면서 $i(i+1)/2=k^2$인 $i$에 대해 1과 2를 swap 했듯이 $i$와 $i+1$을 swap해주는 방식으로 출력했다. Cst, en에 관계없이 어떤 규칙을 가지고 움직여야 될 것 같다는 느낌..

https://codeforces.com/contest/2070  Performance Rating : 2300 A$0$이상 $n$이하의 수 중 나머지가 0, 1, 2인 수의 개수를 찾는 문제였다. $(n/15)*3+\mathrm{min}(n\%15+1,3)$을 출력해 주면 된다. B$x$에서 시작하여 시뮬레이션을 해서 0에서 만나면 끝내주고 0과 만나지 않는다면 0을 출력해 주고 끝낸다. 0에서 시작하는 것으로 시뮬레이션을 다시 해줘야 하는데 이후 0에서 0과 만나기까지 이동한 횟수를 주기로 반복되므로 이를 바탕으로 계산해 주면 되고 안 만나면 그대로 끝내주면 된다. 여기서 0과 만나면 남은 횟수를 주기로 나누고 더해주고 반복문을 종료해주어야 하는데 종료를 안 했다가 WA를 한번 받았다. C처음에 문제..

https://codeforces.com/contest/2072  Performance Rating : 2450 A절댓값이 $p$이하인 수 $n$개로 합이 $k$가 되게 할 수 있는지 판단하고 만들 수 있을 때 필요한 수의 최소 개수를 구하는 문제였다. $\mathrm{abs}(k)\leq np$인지 먼저 판별하고 맞다면 $(\mathrm{abs}(k)+p-1)/p$개가 최소이다. B'-'를 양끝으로 몰고 '_'를 가운데에 배치하고 양끝의 '-'개수를 최대한 동일하게 맞추는 것이 최선이다. '-'의 개수를 $cnt_1$, '_'의 개수를 $cnt_2$라고 하면 $(cnt_1/2)((cnt_1+1)/2)cnt_2$가 답이 된다.  C일단 0부터 시작해서 최대한 큰 숫자까지 쓰고 bitwise or을 해주었..

https://codeforces.com/contest/1998 Performance Rating : 2900 A$(x_c, y_c)$를 중심으로 점대칭 시키는 것이 더 강한 조건이기 때문에 이를 만족시키도록 짰다. B주어진 $q_i=p_i(\mathrm{mod}\;n)+1$으로 잡으면 $i=1$, $j=n$일 때를 제외하고 $p_i+ \;\cdots\; +p_j=q_i+.\;\cdots\; q_j$가 성립하는 $i$, $j$가 존재하지 않기 때문에 답이 된다. C$a_i+median(c_i)$에서 $b_i=1$이라면 $k$번의 실행을 모두 $a_i$에 하는 것이 이득이고 $b_i$가 0인 $i$ 중 $a_i$가 최대인 것과 $b_i$가 1인 $i$ 중 $a_i$가 최대인 것 두 개만 보면 된다는 생각을..