jay153의 PS 일지

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://www.acmicpc.net/problem/18976  코드http://boj.kr/97c257d8f1b74482be14bb8980f3227c Petrozavodsk Programming Camp Summer 2018 Day 3: MIPT Contest K 난이도 : P2 Elapse Time : 15min 문제를 보고 단순화를 해야겠다는 생각이 들었다. 결국 문제를 요약하면 점과 선분들에 의해 몇 개로 나누어져 있는 평면에서 최소비용의 선분을 제거하여 평면이 분리되어 있지 않도록 만들라는 것이었다. 처음에는 분리되어 있는 평면들에 각각 번호를 붙여준 뒤 비용 순으로 선분들을 정렬하고 선분을 기준으로 양쪽에 있는 평면이 같은 평면인지 확인하는 것을 Dsu를 활용해 처리해 줄 생각이었다. 평..

https://www.acmicpc.net/problem/23176  코드http://boj.kr/7d3b2e772d524996bab2a9994f076fe5 2021 KAIST 11th ICPC Mock Competition G 난이도 : D5 Elapse Time : 80min 체력의 상한이 존재하지 않는다면 $i$번째 과정이 끝난 뒤 남은 체력은 $x+a_1+\cdots+a_i$이다. 남은 체력이 누적합과 연관되어 있긴 한데 상한이 존재한다는 것이 문제였다. 체력이 변하는 과정에서 언제 체력이 최솟값이 될지를 생각해 보니 구간합이 최소인 구간의 끝일 것 같다는 느낌이 왔다. 구간합이 최소인 구간을 $[s, e]$라고 하면 $s\leq i\leq e$인 $i$에 대해 $a_s+\cdots+a_i\leq..

https://www.acmicpc.net/problem/8415  코드http://boj.kr/a2cc1f96953c4eb1accf307a94c67719  Algorithmic Engagements PA 2006 7-5 난이도 : P1 Elapse Time : 실패 문제를 보고 이분 매칭의 개수가 $N$개가 될 수 있으면 룩을 놓을 방법이 존재한다는 것이므로 이분 매칭을 하는 것으로 문제를 풀기 시작했다. 매칭을 해놓고 변경할 수 있는 경우의 수를 dp등의 방법을 활용해 세어보는 풀이를 생각해 보았는데 풀이가 생각나지 않았고 다른 풀이를 찾지 못했다. 시간을 두고 생각하다가 정사각 행렬의 determinant를 생각해보게 되었는데 홀짝성만 판단하면 되는 이 문제와 큰 관련이 있을 것 같다는 생각이 들었..

https://www.acmicpc.net/problem/14734 코드http://boj.kr/d53a0455fbfd4d92b9ef11c779e84844 2017 KAIST 7th ACM-ICPC Mock Competition A 난이도 : P1 Elapse Time : 100min 예제를 보고 왼쪽 $(N-1)$줄을 세로로 맞추어 주고, 오른쪽 $(N-1)$줄을 세로로 맞춘 뒤 가운데 두 줄을 세로로 배열하는 풀이를 생각했다. 왼쪽 $(N-1)$줄은 왼쪽부터, 오른쪽 $(N-1)$줄은 오른쪽부터 한 줄씩 세로로 바꾸도록 코드를 짰는데 WA를 받았다. 케이스 고려를 많이 빼먹은 탓이었다. 한 줄을 모두 세로로 바꿨을 때 'U'가 위치해야 하는 부분에 'L' 또는 'R'이 위치하면 다시 'L' 또는 'R..

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://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://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에서는 다른 두 기준을 가지..