jay153의 PS 일지

https://www.acmicpc.net/problem/11858 코드http://boj.kr/413f27bd03ab448dbbdcb68f18d91605 International Zhautykov Olympiad 2014 E 난이도 : P1 Elapse Time : 실패 문제를 보고 $O(N^2K)$ 풀이를 떠올리는 것은 어렵지 않았다. $O(N^2K)$ 풀이는 전형적인 dp 문제였는데 $dp[i][j]$를 $a_1, \cdots, a_j$까지 $i$개의 그룹으로 나누었을 때 가능한 값의 최솟값이라고 정의하면 $dp[i][j]=\underset{k sharaelong님에게 monotone stack을 활용하라는 힌트를 받았고 이를 어떻게 활용할지를 생각해 보았다. dp 식에서 $\underset{k+1..

https://www.acmicpc.net/problem/17097 코드http://boj.kr/a0f7b589826643efb1bcdb0eea351f4b 난이도 : P2 Elapse Time : 40min 예제를 보면서 문제에서 요구하는 사항을 파악했다. 참말쟁이가 $x$명 이상 있으려면 $A_i\leq x\leq B_i$인 $i$가 $x$개 이상 있어야 한다. 이에 따라 모든 $i$에 대해 $A_i$와 $B_i$ 사이에 있는 인덱스에 레이지 세그먼트 트리로 1을 더해놓고 $v[idx]\geq idx$인 최대 $idx$를 찾고자 하였으나 최대 $idx$를 찾는 것에서 막혔다. 레이지 세그먼트 트리를 활용하면 $Q$번의 업데이트도 로그 시간으로 해줄 수 있으므로 최대 $idx$를 찾는 것만 로그 시간안에..

https://www.acmicpc.net/problem/17096 코드http://boj.kr/1465a10980c64389892baa5e346c81c4 난이도 : P3 Elapse Time : 15min 문제에서 $N$과 $M$의 범위를 보니 다익스트라 문제임이 분명해 보였다. 일단 $i$번째 도시를 가는 데 최단경로로 이동해야 하고 경로가 여러 개라면 앞서 사용했던 경로를 최대한 재활용해야 한다. 우선 무지성으로 다익스트라를 짰는데 다익스트라 코드를 보면서 한 첫 번째 관찰은 특정 도시까지의 최단 거리는 항상 이전 노드까지의 최단 거리와 이전 노드와 현재 노드를 잇는 도로의 걸리는 시간의 합으로 표현된다는 것이다. 두 번째로 한 관찰은 $i$번째 도시를 방문할 경로가 정해져 있다면 방문하는 순서와는..

https://atcoder.jp/contests/arc193   Performance Rating : 1400 AA와 B 모두 처음에 풀이가 떠오르지 않았는데 A 솔브수가 올라가는 속도를 보고 A를 먼저 풀었다. 이 문제는 $[L_i,R_i]$에서 겹치지 않는 구간을 활용하여 $[L_j,R_j]$에 도달하는 문제인데, 도달하는 과정에서 최소한의 $w$를 사용해야 한다. $L_i\leq L_j$라고 하자.  $[L_i,R_i]$와 $[L_j,R_j]$가 겹치지 않으면 바로 이동하는 것이 최선이고 중간에 3개 이상의 구간을 거치는 경우 하나를 제외시키고도 충분히 도달 가능하다는 것을 깨달았다. $R_p\mathrm{max}(R_i,R_j)$인 경우 $p$번 노드 하나만 거치고도 도달할 수 있고 $R_iR_..