문제풀이 흑마법

언제나 그렇듯이 잘 풀리면 상관 없는 것들

내적 해시

- 존재성만 확인하면 되는 상황이라면 굳이 복잡한 라빈카프가 아니라 랜덤 포인트 N개를 뽑아 내적해시를 사용할 수 있다.

 

https://github.com/Pentagon03/Algorithms/blob/master/Strings/Hasher_Dot.cpp

 

시간제한만큼만 최선을 다하기

최적해를 구해야 하는 상황에서 충분히 빠른 방법이 생각이 안 날 경우, 그냥 가능한만큼만 브루트포스로 찾아본다 ?!

적당한 시간 제한을 걸어놓고, 브루트포스 / 백트래킹이 그 시간을 넘었을 경우, 그때까지 찾은 답을 출력한다.

예시1 https://codeforces.com/contest/1979/submission/264506642

예시2 https://www.acmicpc.net/problem/2409

 

 

적당히 몇개만 뽑아서 검사하기

정답이 충분히 큰 크기의 부분집합에서부터 나온다고 확신할 수 있을 경우, 랜덤으로 O(sqrt N)개 정도만 검사해서 최적값을 갱신해준다.

이떄 유의할 점은 N이 충분히 작은 경우 그냥 전체를 돌려야 WA를 안 받는다.

예시 https://codeforces.com/contest/1977/submission/262767998

 

(구현 팁) If문 한줄로 쓰기

무언가 출력하고 바로 return 해야 할 때 return과 cout을 붙여써서 귀찮은 중괄호를 피할 수 있다.

int solve(){
    int x = 3;
    if(x>0)
        return cout<<"Positive", 3;
}

void solve(){
	int x = 3;
    if(x>0)
    	return cout<<"Positive", void();
}

 

(구현 팁) 다차원 VLA(Varibale Length Array)

PS에서 전역배열을 쓰면, 1. 사용하는 부분과 멀어지고, 2. 코포식 테케 문제의 경우 매번 반복문으로 초기화를 해줘야 하는 불편함이 있다.

이를 해결하기 위해 흔히 채택되는 대안은 std::vector이다. 다만 다차원 벡터를 쓸 경우 정말 의미 없이 코드가 길어진다는 단점이 굉장히 크다. 초기화 하기 위해서는 다음과 같은 코드를 작성하거나, 반복문을 써야 한다. 굉장히 귀찮다.

vector<vector<vector<int>>> v(n, vector<vector<int>>(m, vector<int>(k)))

 

그래서 VLA를 써주면 함수 내에서 유용하게 정해진 값을 가지는 다차원 배열을 만들 수 있다.

C++ 표준이 아니며, GCC에서만 동작하는 것에 유의할 것.

int n, m, k; cin>>n>>m>>k;
int A[n][m][k];

이제 {{{0}}} 등으로 초기화 안하면 의미 없는 거 아니냐? empty initializer list를 써도 컴파일 에러는 안 나지만 저건 UB고, 동작 안한다. 보통 UB 중에서도 동작 하는 것들이 종종 있는데, 저건 진짜로 안된다. 

 

그래서

#define INIT(v, x) memset(v, x, sizeof v)

등의 코드를 넣어서 VLA를 만든 후 바로 초기화를 해주는게 좋다.

 

다만 표준이 아니다보니 굉장히 불안정한 면이 있다. https://codeforces.com/blog/entry/112861

람다 같은거 같이 쓸 생각말고 그냥 define으로 쓰자!

Bitset, simd로 뚫기

bitset의 /64는 정말 강력하고 유의미한 최적화다

예시1: 정해가 bitset이다.  https://www.acmicpc.net/source/share/680990fdf04d4b518126fc4abac88f2d

예시2: dfs 최적화로 0ms를 받는다 -> https://www.acmicpc.net/source/share/0194d94e34274624935c0d6b78c90af9

더 많은 예시: https://codeforces.com/blog/entry/73558

 

테케 문제의 경우 tr2의 dynamic_bitset을 활용하자: https://codeforces.com/blog/entry/129454

64bit bitset으로 2배 빠르게 만들 수 있다: https://codeforces.com/blog/entry/77480

 

 

simd는 아래에서 공부해보자

https://codeforces.com/blog/entry/98594

https://justicehui.github.io/hard-algorithm/2021/11/15/simd-in-ps/.

https://m.blog.naver.com/PostView.naver?blogId=jinhan814&logNo=222322477829&categoryNo=6&proxyReferer=

 

Local Search Algorithms

인공지능에서 사용되는 기법인 지역 탐색으로 문제를 해결할 수 있는 기하 문제들이 있다.

 

https://blog.com24everyday.com/entry/%EC%9D%B8%EA%B3%B5%EC%A7%80%EB%8A%A5-4Local-Search-Algorithms

 

예시: https://www.acmicpc.net/problem/17625

 

 

---

다른 백마법들

https://codeforces.com/blog/entry/100910