jay153의 PS 일지

https://atcoder.jp/contests/abc398  Performance Rating : 1684 A$N$이 홀수일 때와 짝수일 때 나누어 출력해 주었다. B각 숫자의 개수를 세준 뒤 정렬하고 가장 큰 수가 3 이상, 두 번째로 큰 수가 2 이상인지 확인하였다. C각 숫자의 개수를 map으로 세준 뒤 다시 한번 순회하면서 개수가 하나인 수 중 가장 큰 수의 인덱스를 출력하면 되는데, 가장 큰 인덱스를 출력하는 것인 줄 알고 WA를 한번 받았다. D연기의 좌표를 옮기는 것보다 기준점의 좌표를 옮기는 것이 낫겠다는 생각을 했다. map에 $(0,0)$의 기준점 기준 위치를 1로 바꿔주고 $mp[(x+r, y+c)]$를 출력해 주는 방식으로 해결했다. E짝수 사이클을 만들면 안 되는 것으로 문제를..

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$를 어떤 순서로 사용할지에 따..

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://www.acmicpc.net/contest/view/1455  A2024년 7월 기준 $7(n-1)$개월이 지났을 때 몇년 몇월인지 구하는 사칙연산 문제였다. B나이트가 2번 이동했을 때 같은 색 칸으로 이동한다는 것으로 우선 $n\geq 4$인 경우에 대해 밝은 색, 어두운 색 칸의 개수를 세는 것으로 답을 구했다. $n$이 3이하일 때 답이 달라지는데 이를 예외처리 해주었다. C$p^{q^r}$의 경우 $p>1$, $q>1$인 경우에 대해 매우 큰 값을 가지기 때문에 $p=1$인 경우와 $q=1$인 경우에 대해 더하는 것이 답이 될 것이라고 생각했고 맞았다. D1, 5의순서와 무관하게 답을 구할 수 있어야 하므로 3의 배수가 가장 적합할 것이라고 생각했다. 각 자리의 합을 구해놓고 3의..

https://atcoder.jp/contests/abc397   Performance Rating : 2335 A기본적인 대소관계 비교 문제였다. B$i$번째와 $(i+1)$번째 사이에 문자를 삽입하면 $1$부터 $i$번째까지 문자의 위치에는 영향을 주지 않기 때문에 앞에서부터 채워 나가야겠다는 생각으로 풀었다. C가장 처음 생각난 풀이는 레이지 세그먼트 트리였으나 조금 더 생각을 해보니 각 숫자의 개수를 세어두면 $A_1$부터 차례로 보면서 왼쪽과 오른쪽에 있는 숫자 종류의 개수를 $O(1)$의 시간에 구할 수 있다. D처음에는 풀이가 떠오르지 않았다. 투 포인터로 $x$, $y$를 찾아나가는 풀이가 가능한지 생각하기 위해 가능한 $x$의 범위를 생각해 보기로 했다. $(x+1)^3-x^3=3x^2+..

https://www.acmicpc.net/problem/29441  코드http://boj.kr/5a53c2b9a48c4aa1b32320178de76059 Russian Olympiad in Informatics 2011-2012 Season A 난이도 : P3 Elapse Time : 15min 처음에는 여러개를 xor할 수 있는줄 알고 가우스 소거를 할 생각을 했다. 그러나 하나만 xor하는 것이었고 다른 풀이를 생각하기 시작했다. xor연산이기도 하고 가장 큰 값을 만드는 것이 목적이므로 큰 비트부터 그리디하게 처리하면 되겠다는 생각을 했다. 이를 시간 안에 처리하기 위해 정렬을 해놓고 범위를 줄여나가는 것이 가능하겠다는 생각이 들었다. 30번째 비트부터 보면서 현재 비트가 몇인 것이 유리한지, ..

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