jay153의 PS 일지

https://www.acmicpc.net/contest/view/1531 6월 말에 UCPC를 같이 나가자고 했던 gs25와 sharaelong의 연결으로 알게 된 gina님과 나로 UCPC 팀이 결성되었다. 팀이 늦게 결성되었다 보니 예선을 나와 gs25 둘이서 쳐서 통과한 뒤 팀 연습을 두 번 하고 본선을 치르게 되었다. 최종적으로 10등 4등상을 받게 되었고 생각했던 것 보다 좋은 결과가 나와서 만족스럽다. I (+, 0:09)정렬하고 배열의 값이 모두 0이라면 0, 아니라면 $mex+1$의 값을 출력하는 문제이다. 대회 시작하고 쉬워보이길래 내가 잡았다. E (+, 0:31)스코어보드를 보니 많이 풀렸길래 gina와 gs25가 풀이를 같이 생각하고 풀었다. C (+1, 1:01)gs25가 풀이..

https://www.acmicpc.net/contest/view/1525 신청 마감 3일전에 팀이 결성됐다. 팀은 겨울방학 때 코포 공부를 같이 했던 gs25와 sharaelong의 소개로 이어진 gina님이었는데, 예선 때 gina님께서 시간이 안된다고 하셔서 예선은 나와 gs25 둘이서 진행했다. 둘이서 예선을 통과할 수 있을지 애매하다고 생각했는데 생각보다 대회 당시 풀이를 금방금방 떠올려서 22위로 무난하게 예선을 통과했다. 초반 한시간 정도는 gs25가 A~F, 내가 G~K를 보고 각자 문제를 풀다가 이후에는 스코어보드를 보면서 같이 생각하면서 풀었다. A (+, 0:03)gs25가 풀어왔다. B (+, 0:07)gs25가 풀어왔다. C (+, 2:17)G를 풀고 C로 넘어왔다. gs25가 나..

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홀수 인덱스를 가진 부분과 짝수 인덱스를 가진 부분이 정확히 분리되어 있다는 생각을 했다. 우선 알파벳들의 분배를 적절히 잘했을 경우 ..