구간을 pair<시작점, idx>으로 정렬하고 <끝점, idx>으로도 정렬한 2개의 배열이 있으면 한 점이 몇개의 구간에(혹은 어떤 구간들에) 포함되는지 여부 구하기. 세그트리 lazy로 구간마다 1증가하고 점으로 query를 날리면 전처리 nlogn에 쿼리logn 된다. 다만 한번만 구하는건 나이브한 O(N)이 더 나음.
4. LIS 정렬
A[0]를 포함하는 LIS를 찾아서 제거하고
남은 배열에서 또 위 작업을 텅빌때까지 계속한다.
그렇게 찾은 LIS를 병합하면 정렬된다.
그 LIS들을 최대한 빠르게 구하는 방법은?
6. BOJ 14889 Large 버전
내 코드가 2^(N/2) * n이고 일반적 풀이가 2^(N/2)*n^2이다.
7. 병든나이트 최대방문수 아니라 방문가능한 위치의 수 버전. 1000*1000정도의 사이즈로 간단한 dfs문제로 하자.(커질수록 패턴이 있는건 맞는듯 하나 너무 구데기다)
8. 늑대3
늑대1, 늑대2 문제를 MCMF로 풀어보자. Delight for a Cat의 아이디어 활용하면 될듯.
최단경로의 개수
플로이드 변형. min점화식을 +로 바꾸고 기저사례를 1로 주면됨. 쿼리로 s,e주고 개수출력하라하면 되겠다. 입력이 너무 커지니까 정점별로 시작정점별 최단경로개수를 출력하는것(V줄 출력)으로 해도 좋을듯. 그러면 시작정점별 최단거리인 끝점들의 경로갯수합이 답이겠다.근데 구현이 더러워질거같으니 첫 방식에서 쿼리를 조금만 주는거로 해보자. 다익스트라로 뚫리는건 고려하지말자. 다익으로 풀면 푸는것이지.
트리와쿼리 3(Hard)
쿼리가 (1, v)꼴로만 주어지지 않고, 임의의 (u,v)꼴로 바꾼 버전. 내 풀이가 이것도 커버한다. 교환법칙 의존성 없이 짰기 때문이다.
뒤집기연산 이중연결리스트 O(1) 사용하는 문제(BOJ-3444 Robotic Sort 참고)
LIS Segment Tree 풀이로 쿼리화 가능할까?
절댓값은 LIS인데 부호가 계속 반전되는 수열 최대길이
거리가 더하기가 아니라 max인 계에서 다익 될까?
화성지도(직사각형 합집합 넓이) 와 쿼리(처음 잘못짰던 query 활용해서 N^2 스캐폴딩으로 검증하면 될듯)
GF(7) 같은 역원있는 유한체상의 가우스소거법 문제? 길이 n의 1차원배열이 처음에 다 0이었다. M개의 패턴을 사용하능하고, 각 패턴의 길이는 모두 n이다. 패턴을 사용하면 해당위치의 값이 1 증가한다. A가 몇개를 적용한 결과가 주어질 때, 각 패턴에 대해 몇번 사용해서 만들어진건지 스페셜저지. 패턴길이 짧게하고 거의 모든 n개 위치에서 사용할 수 있게하고 패턴개수를 10개정도로 해도 될듯. 1차원 배열로 이야기했지만 2차원배열도 같은문제가 됨.
무방향 그래프가 주어진다. 각 간선을 방향화하여 만들어지는 방향그래프의 SCC의 최소 개수는? 최대 개수는?
최소: BCC 아닐까?
최대: 방향을 DAG가 되도록 주면 정점 개수와 같은듯.
SWEA 9487 포교 쉬운버전: 한곳에서 시작하는거만 해도 DP식 세우기 어려운듯. 시작점을 루트로하는 트리에서 d[i]=모든 자식 j에 대해, min(d[j]+(d[j]보다 크거나 같은값을 가지는 자식들 개수))로 풀 수 있지 않나? 추후에 원본문제 답 확인후 정당성 증명하면 적당한 난이도일듯. 쉬운버젼 똑같은문제가 백준에 있다.(boj1135뉴스전하기)
가우스정수의 소수체 문제? Boj9464문제 풀다가 {x+y(1-sqrt(2))}{x+y(1+sqrt(2))}=L 꼴이 나와서 든 생각이다. 물론 저 문제는 가우스소수로 못푼다. 가우스소수 인수분해꼴이 나오는 식으로 적당히 만들면 되지 않을까?
boj3056 제한 큰 버전: 내 풀이가 확률의 곱에 로그씌워서 로그들의 합으로 만들어서 최대가중치매칭 찾는것이다. 헝가리안 가능. 소수오차 없지 않을까....? 확률이기 때문에 입력 정밀도가 작으니 괜찮을지도 모르겠지만 확실히 검증하고 사용하자. 이미 그렇게 푼사람 많은듯. 0초가 다 그런듯. 다익스트라나 다른거에 응용해서 만들어보자. Hansc0320코드가 log없이 mcmf쓰는걸 보니 오차없이 변형가능한듯. 잘 참고해보자. 역으로 합을 곱으로 만드는 지수법칙으로 fft같은걸 쓰는문제는 정밀도문제가 없을테니 생각해볼만한듯
Boj.kr/8012 방문순서 상관없는버전: 문제 잘못읽어서 순서상관없이 풀었었다. 이 경우 솔루션은 방문해야할 필요가 없는 리프들을 가능한만큼 계속 제외하고 남은 트리의 (간선개수*2-트리의 높이)가 된다. 간선개수*2까지 구한 코드는 아래에 있다.
const int N=3e4;int n, m, a[N];Arr<int> g[N];
int dfs(int v, int p){
int r=a[v]?0:-inf<int>();
for(auto i:g[v])
if(i!=p){
auto z=dfs(i,v)+2;
r+=max(0ll,z);
r=max(r,z);
}
return r;
}
signed main(){
cin>>n; rep(i,n-1){ int a,b; cin>>a>>b; a--,b--; g[a].pushb(b); g[b].pushb(a); }
cin>>m; rep(i,m){ int x; cin>>x; x--; a[x]=true; }
cout<<dfs(0,-1)<<endl;
return 0;
}
문제이름 추천: 낭만고양이
간선 하나만 음수인 다익스트라: 그 간선 없이 다익, 그 간선을 무조건 지난다고 가정하면 그 간선의 양 끝에서 s,e까지의 거리로 잘 할수 있음.
NlogN 선분교차판정으로 환원되는 문제는 어떨까?
최소컷? DP확장하는 LP? 플로우? 같은 문제도 좋을듯
scpc 구두제작 변형: 한 단위시간동안 일할 수 있는 장인의 수가 제한되있는 조건 추가: 시간정점 분할하여 제한하는 용량할당: (대략적인 디스크립션)작업실이 좁기때문에 최대 K명의 장인만 동시작업이 가능하다