N coding

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109#include #include #include #include using namespace std;#define inf 10000000 int n, a, b, c, k, d, e;int mx = 0, mn = inf;int par[100001][21], maxx[100001][21], minn[100001][21];i..

계속 전함을 segment tree에 넣을 생각만 하고 있어서, 전함을 w 가 큰 거 부터 넣는다.끝나는 지점에 w를 넣고 시작지점-1 에 -w를 넣어서 레이저를 x부터 N까지 합을 구해볼까 등등..근데 이것저것 다 고민해도 삭제가 가장 걸림돌이 되었다. 그러다가 레이저는 기준점이 하나잖아? 라는 생각에서 레이저를 segment tree에 넣으면 모든게 챡챡 풀린다는 것을 깨달았다. 1. 레이저가 x점기준, y점기준으로 들어오니까 각각을 나눠서 세그먼트트리를 2개를 만든다.2. 세그먼트 트리는 좌표를 (좌표압축해야함) 표현하고 있고 안에 들어있는 값은 그 좌표를 뚫는 레이저의 가장 작은 인덱스이다. (가장 먼저나오니까)3. 각각의 전함의 x1 - x2 를 x좌표 세그트리에 넣어서 그 사이를 뚫는 레이저의..

되게 막연하게 생각되었는데처음에는 10^6이고 총 사용할 수 있는 엣지가 60개니까 1 -> 2 로 갈 때 0 ~ 9 * 10^i로 표현하려고 했다.근데 10진수로 하니까 L보다 큰 수를 막는 게 너무 어려워서 2진수로 방향을 틀었다이때 최대 노드 N이 20이고, 10^6이 최소 20개의 비트로 표현되므로 딱 맞다. 좀 거지같이 그리긴했지만이런 느낌으로 표현하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include #include #include #include #include #include #include #inclu..

고통받은 문제 어렵진 않은데 처음에 문제 잘못생각해서 겁나 어렵게 생각하다가 그래프 구성 못하고 가만히 있다가잘못생각했다는 걸 깨닫고 짰는데 또오 출력 바로 하려고 하다가 오지게 틀린 문제다.결과값 개수를 이미 들은 것중에 후보에 나온 애들의 개수를 세서 totalflow에서 빼서 출력했는데생각해보니 그러면 음수값이 나올수도 있어서... 당연히 틀리는 코드였다 ㅠ 사전순으로 출력이 아니라면 그냥 유량으로 쉽게 풀리는데사전순으로 출력이어서 mcmf로 풀었다.이미 들은 과목이면 반드시 포함시키는 게 이득이니까 그럴수 있게 가중치를 0으로 주었고그렇지 않은 과목이면 사전순으로 가중치를 주었다. 이분매칭으로 푸신 분도 있고, 그냥 유량으로 푸신 분도 있더라 123456789101112131415161718192..

구현거지라서 고생함 i, j 까지 오는 세 점의 최단거리를 구하자 1) 두 죄수가 다른 탈출구로 나오는 경우 2) 두 죄수가 같은 탈출구로 나오는 경우 2번의 경우엔 그냥 각각 최단거리 구해주면 됨 1번의 경우엔 외부에서 들어오는 거 + 죄수1에서 나가는 거 + 죄수2에서 나가는 거 - (만약 그 점이 #이라면 겹치는 거 2 빼줌 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192#include #include #include #include #..

나는 이분탐색 + 유량으로 풀었는데, 사실 가중치가 1이라서 그냥 이분매칭이다.주차장 문제랑 좀비 아포칼립스 문제를 짬뽕시킨 느낌이었다.아마 이분 매칭이면서 시간에 따른 정점 분리도 해서 그런 것 같다. 탈출구를 시간에 따라 정점 분리를 해줬다. 1초일때의 탈출구, 2초일때의 탈출구... 그리고 각각 1의 가중치로 sink와 연결빈칸인애들은 가중치 1로 source와 연결해준다. (이 때 가중치 = 유량은 사람을 뜻함)빈칸이나 벽인 애들은 굳이 해 줄 필요가 없다. 그리고 빈칸에서부터 탈출구까지의 거리를 구했다.이 때 나는 모든 빈칸을 출발지로 하고 bfs를 돌렸는데, 플로이드 워셜로 하신 분도 있고아니면 탈출구의 갯수가 (일반적으로) 더 적으니까 탈출구를 기준으로 bfs 돌려도 될거같다. 정점개수가 작..

Manacher's Algorithm 시간복잡도 O(N) 문자열의 길이 N만큼의 숫자 배열 A를 만든다. 이 때 A[i]는 i를 중심으로 한 팰린드롬의 최대길이이다. -> str[i-a[i] : i + a[i]] 는 팰린드롬 문자열이고 str[i-a[i]-1 : i + a[i]+1] 은 팰린드롬이 아니다. 알고리즘 진행 1. i 는 0 ~ N-1까지 진행된다. 2. j r 인 경우, i 이전의 팰린드롬 중 i를 포함하는 팰린드롬이 없다. A[i]는 0 i str[h + A[h] +1] != str[h - A..

해야 하는 것 1. 접두사 == 접미사인 애들의 길이를 찾는다.2. 걔네가 몇 번 나오는지 찾는다. 내가 문자열과 쿼리를 푼 방법으로 찾았다. 접두사 == 접미사이려면 suffix array를 구했을 때, 1. 원본 문자열과 lcp가 존재해야하고, 그 lcp의 길이가 자기 자신의 길이와 같아야한다.2. 그리고 그 cnt는 원본 문자열과 자기 자신의 sa상에서 떨어진 거리이다. sfx상에서 원본 문자열보다 위쪽에 있는 애들은 그냥 구해주면 된다.아래쪽에 있는 애들도 그냥 구해주면 된다.다만 위쪽에 있는 애들이 아래쪽에도 계속 공통으로 나올 수 있고그 한계는 자신의 길이보다 짧은 lcp가 나올때 이므로 minn값이 바뀔때마다그 minn길이의 ans가 있는 지 확인한 후 있으면 cnt를 넣어주었다.더해줄때 하..

진짜 극혐... 어제부터 계속 붙잡고 있었다.딱히 붙잡고 있을만큼 영양가 있는 문제는 아니었는데이게 풀이가 suffix array랑 아호코라식 두개가 있는데 suffix 풀이가 궁금해서 내가 그나마 풀 수 있는 아호코라식으로 열심히 비벼봄..ㅠcoci에 솔루션은 있는데 정답 코드가 없다. 일단 나는 보자마자 아호코라식이 생각나서 그걸로 접근했다-> 26*4*5000*5000하면 당연히 메모리 터짐그냥 Trie면 내가 아름다운 이름을 푼 방식이나 그렇게 접근할텐데아호코라식이라 queue에서 bfs를 돌 때 구하기 좀 빡세서.. 쥬륵map으로 해봐도 안되고 -> 근데 아름다운 이름에서도 map을 써본 결과 map은 딱히 메모리를 엄청나게 줄여주진 않는 거 같다. 얘는 쓸때마다 터짐결국 질문검색에서 찾다가 v..

구현문제 나는 삼성 B형 연습중이었어서 dfs말고 bfs쓰고, queue도 직접 구현하였다. 디코딩하고 그림을 찾아내면 된다. 그림은 그 내부의 빈공간의 개수를 기준으로 찾으면 됨. 나는 일단 검은부분을 각각 idx를 올리면서 구해주고 - 각각의 그림은 다른 값을 갖게됨 다음으로 하얀부분에 들어가는데 그 하얀부분이 만나는 검은 부분의 값이 한 개일때 idx의 내부빈공간++을 해줌 그리고 counting sort로 출력~! (외부로 나가는 건 또 따로 처리) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747..