jay153의 PS 일지

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://www.acmicpc.net/problem/28059  코드http://boj.kr/e459a94c63ce440d97b82cb50426bec6 2023 KAIST RUN Spring Contest G 난이도 : D4 Elapse Time : 60min 문제를 보고 한 첫 번째 추측은 $s$에서 최댓값을 남겨놓고 마지막에 사용하는 것이 이득일 것 같다는 것이었다. 최댓값을 제외한 $n-1$개의 수로 최대한 작은 숫자를 만들어놓고 최댓값과 마지막에 묶어주는 전략을 세웠다. 예제를 분석하면서 한 두 번째 추측은 $n-1$개의 수 중 몇 개를 골라 두 그룹으로 나누는 모든 경우 각 그룹의 숫자 합의 차 중 최솟값을 만들 수 있을 것 같다는 것이었다. 두 번째 추측이 맞다면 최댓값 대신 다른 수를 ..

https://www.acmicpc.net/problem/1635 코드http://boj.kr/33d5f3fa46b445aeb0c5ad76a78e0ab1 난이도 : P5 Elapse Time : 10min 처음에는 주어진 $M$개의 수열에 맞춰서 $N$개의 수열을 만들 생각을 해보았지만 수열의 가짓수가 너무 많고 예외 처리를 많이 해주어야 할 것 같아 다른 방법을 생각해 보기로 했다. 우선 조건을 더 강하게 바꿔서 어떤 수열이 주어지든 $N$개 중 하나의 수열을 곱했을 때 수열값이 0이 되게 만들 수 있는지를 생각해 보았다. $N$개가 제한이므로 전체가 1인 수열에서 앞에서부터 $k(0\leq k\leq N-1)$개 까지의 수가 -1인 $N$개의 수열을 준비하면 어떻게 될지 먼저 생각해보았다. 전체 다 ..

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://www.acmicpc.net/problem/25414 코드http://boj.kr/f3de6e6220654d93aaa53a55a98a0280업솔빙http://boj.kr/15a136f934dd42349cf2c778d88cc50f 난이도 : P1 Elapse Time : 실패 문제를 보고 #11858과 비슷하다는 느낌을 받았다. 이 문제에서는 구간을 남길 이유가 없기 때문에 결국 주어진 수열을 $K$개의 구간으로 쪼개는 문제가 된다. 그래서 #11858에서 사용했던 스택을 사용할 수 있는지 살펴보았는데 #11858에서는 최댓값만 관리하기 때문에 monotone stack으로 값을 관리하기 쉬웠지만 이 문제에서는 최댓값과 최솟값 모두를 관리해주어야 하기 때문에 스택으로 푸는 것은 무리가 있어 ..

https://www.acmicpc.net/problem/26399 코드http://boj.kr/6e9dc3dd260c444491dc44c13cdde2ef COCI 2022/2023 Contest #2 3 난이도 : P1 Elapse Time : 실패 문제를 보고 30분 동안은 어떤 것도 떠오르지 않아 생각만 했다. 30분간 고민한 뒤 생각한 것은 길이 200000짜리 bitset을 만들어서 $k$번째 색깔의 램프는 bitset의 $k$번째 원소에 표시를 해놓고 2차원 누적합을 만들어 놓는 것이다. 직사각형 영역 내 모든 bitset을 xor 했을 때 bitset의 모든 원소가 0이 되면 그 직사각형에는 모든 램프가 쌍을 이루는 것이 보장된다. 하지만 $O(nmk)$의 공간복잡도를 감당할 수 없었고 풀지..

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://www.acmicpc.net/problem/17668 코드http://boj.kr/c12e64a1abaf44e6962f0cbae0872a06 JOI 2018/2019 Spring Training Camp 1-1 난이도 : D5 Elapse Time : 65min 값의 업데이트가 없어 오프라인 쿼리로 처리 가능하다는 것이 눈에 먼저 들어왔다. 가장 먼저 한 생각은 기준 3가지 중 정렬을 통해 1가지를 줄이는 것이었다. 학생들의 시험 점수쌍을 $S_i+T_i$를 기준으로 정렬하고 마찬가지로 쿼리도 $Z_j$를 기준으로 정렬하면 각 쿼리에서 점수 합 기준을 만족하는 점수 쌍들만 가지고 판단할 수 있다. 여기까지는 그냥 #2336과 비슷한 문제라고만 생각했지만 #2336에서는 다른 두 기준을 가지..

https://www.acmicpc.net/problem/7783 코드http://boj.kr/3bb472b769d84eae85fb645da11bbf8d KBTU Open 2008 B 난이도 : P2 Elapse Time : 30min 우선 직사각형 2개를 골랐을 경우 어떤 이유에서든 각 직사각형은 상하좌우로 확장될 수 없다는 것을 먼저 생각했다. 그 후에는 먼저 직사각형 1개에 대해 가장 큰 직사각형을 구하는 방법에 대해 고민했다. 고민을 하던 중 행렬의 한 행을 bitset으로 저장해 놓으면 어떻게 될지 생각을 해보았다. 어떤 직사각형이 $i$번째 행부터 $j$번째 행까지 걸쳐있다고 할 때 $i$번째 행부터 $j$번째 행까지 bitwise or 연산을 해주었을 때 0인 열에만 직사각형이 존재 가능하다..

https://www.acmicpc.net/problem/19045 코드http://boj.kr/3abe2ed846844c988d8e303c5c2bc55f Petrozavodsk Programming Camp Summer 2017 Day 2 C 난이도 : P1 Elapse Time : 40min 처음에는 '#'으로 되어 있는 부분을 BFS로 묶은 뒤 떨어지는 거리를 계산하려고 하였으나 예제처럼 블록 안에 블럭이 들어있는 경우에 떨어지는 칸 수를 계산하기 쉽지 않았다. 관찰을 해보니 특정 블럭이 떨어지는 칸수는 그 블럭의 열별 최하단 '#'과 그 바로 아래에 있는 '#'인 칸이 떨어지는 칸수와 그 칸과 블럭 사이에 있는 '.'의 개수에 영향을 받는다는 것을 알게 되었고 이는 다익스트라와 BFS를 적절히 섞..