jay153의 PS 일지

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이 존재한다면 두 값은 같을 것이고 ..

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_..

https://www.acmicpc.net/problem/3999 코드http://boj.kr/c617274fbc344cd39f524bd87344d40c ICPC Northern Eurasia Finals NEERC 2012 J 난이도 : P1 Elapse Time : 50min 문제를 보고 #2301과 비슷하다는 생각은 했는데 점프의 거리가 1, 2, 3만으로 이루어져 있다는 것이 풀이를 떠올리기 힘들게 만들었다. 처음에는 0 3 2 1 4와 같은 단위 움직임을 여러 개 만들어 놓고 주어진 $a$, $b$, $c$에 따라 단위 움직임들을 조합하여 풀 생각을 했으나 단위 움직임을 몇 개 만들어서 조합해도 만들어지지 않는 극단적인 조합들이 존재했다. 그래서 다른 접근의 필요성이 느껴졌고 1짜리는 혼자 있어..

https://www.acmicpc.net/contest/view/1450  A$\mathrm{min}(t_1,t_2)$를 구하는 문제였다. B전형적인 스택 문제라는 생각이 들었다. 검사하는 문자열도 "skeep"으로 5글자이기 때문에 매번 스택의 뒷 5글자가 "skeep"인지 검사를 해도 된다. 스택에 문자를 하나씩 집어넣고 "skeep"이 나온 경우에는 뒷 2글자를 추가적으로 보면서 "skeep"이 최대한 많이 나오도록 글자를 넣어주었다. C스코어 보드를 보고 J가 많이 풀렸길래 J로 가려고 했는데 J인 줄 알고 C를 먼저 풀었다. 문제를 보고 3분 만에 풀린 문제 치고는 너무 어렵다는 생각을 했지만 내가 부족해서 그렇다고 생각하고 풀기 시작했다. 문자열에 처음 J가 나올 때 빼고는 점프를 할 때 나..

문제 링크 코드http://boj.kr/942a617eb273499fa12250bd1e91dfb5 2023 충남대학교 SW-IT Contest Division 1 K 난이도 : P3 Elapse Time : 70min 어떤 위치가 며칠 후에 꽃이 필지 구해보면 그 위치에서 초기에 꽃을 심은 있는 위치들과의 거리 중 최솟값이 된다. 모든 위치에서의 값 중 최댓값을 구하는 것이 이 문제의 요구사항이다. 이 문제에서 가장 눈이 간 것은 $M$에 비해 $N$의 범위가 작다는 것이다. 처음에는 모든 위치 중 어떻게 위치의 후보를 줄일지 생각했다. 하지만 $K$개의 점들의 위치 관계가 항상 달라지는데 이를 일반화하기는 쉽지 않아 보였다. 두 번째로 한 생각은 파라메트릭 서치가 사용 가능한지이다. 그러나 방법이 쉽게..

https://www.acmicpc.net/problem/17050  코드http://boj.kr/70deeac7b2b2446487665d909f26a5a0 Croatian Open Competition in Informatics 2018/2019 Contest #5 난이도 : P4 Elapse Time : 25min 문제를 읽고 트라이를 쓰면 편할 것 같다는 느낌이 들었다. '?'가 처리 가능한지와 '?'를 처리할 때 시간 복잡도가 커지지 않는지가 관건이었다. 트라이에 '?'가 포함된 단어를 삽입할 때와 트라이에서 '?'가 포함된 단어와 일치할 수 있는 단어의 개수를 세어 답에 더해줄 때 2가지를 처리해야 했다. '?'가 포함된 단어를 삽입하는 것은 트라이를 만들 때 인덱스 하나를 추가해 주면 되기 때..

https://www.acmicpc.net/problem/14849 코드http://boj.kr/bbf8635a8ab74ad7bfe625ff7021af42 난이도 : P2 Elapse Time : 90min 이 문제를 보고 $T=100$, $q=100$, $v=10^5$인 것이 먼저 눈이 들어왔다. $O(Tqv)$의 코드는 시간에 안 들어올 것이기 때문에 $c_1$, $c_2$, $c_3$, $c_4$를 입력받고 쿼리를 입력받기 전에 무언가를 미리 계산을 해놔야겠다는 생각을 했다. 동전을 무제한으로 사용 가능할 때 $x$를 만드는 경우의 수를 구해놓으면 쿼리 처리를 할 수 있을지 생각해 보았다. 쿼리에서는 동전 개수에 제한이 있는데 포함과 배제로 제한보다 많이 사용하는 경우를 빼주는 것은 동전 종류가 4..