jay153의 PS 일지

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를 적절히 섞..

https://www.acmicpc.net/problem/16531 코드http://boj.kr/0b3b16452bad451897d1fd5844b4292b ICPC Latin America Regional Contests 2018 K 난이도 : P2 Elapse Time : 20min 문제를 보고 예전에 풀었던 #8230과 비슷하다는 생각을 했다. #8230에서도 정렬을 하고 가장 작은 것과 다른 수의 비교로 문제를 풀었기에 여기서도 정렬을 해놓고 비슷하게 하면 되지 않을까 싶었다. #8230과의 결정적 차이는 여기서는 $2^N$개의 조합을 모두 본다는 것이었다. 이를 바탕으로 한 첫 번째 관찰은 가장 작은 값은 모든 음수를 다 더한 값이 되고 두 번째로 작은 값은 0이 존재한다면 두 값은 같을 것이고 ..