unordered_map에 사용자 정의 해시 함수 사용하기

unordered_map의 템플릿 인자에 직접 정의한 해시 함수를 넣어서 [핵 피하기] or [원하는 자료형을 key로 사용하기] 를 할 수 있습니다.

key의 자료형을 바꾸자

20940번: Pingvin 문제를 깔끔하게 풀고 싶은 마음에 이상한 짓을 했습니다.

 

다음 코드는 Pingvin 문제에서 456ms로 AC를 받은 코드입니다. 상수 최적화 없이는 TLE가 나기 쉬우므로 주의하세요.

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
using namespace std;

using iii = array<int,3>;

struct custom_hash {
    size_t operator() (const iii &a) const {
        return (a[0]) ^ (a[1]<<7) ^ (a[2]<<14);
    }
};

int n;

const iii d6[] {{1,0,0},{-1,0,0}, {0,1,0},{0,-1,0}, {0,0,1},{0,0,-1}};
bool out(const auto &x) {
    for (const auto &e : x) if (1 > e or e > n) return true;
    return false;
}
iii operator + (const iii &l, const iii &r) {
    return {l[0]+r[0],l[1]+r[1],l[2]+r[2]};
}

iii S, E;
unordered_set<iii,custom_hash> a;
unordered_map<iii,int,custom_hash> dist;
queue<iii> q;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    rep(i,0,2) cin >> S[i];
    rep(i,0,2) cin >> E[i];
    
    rep(k,1,n) rep(i,1,n) rep(j,1,n) {
        char c; cin >> c;
        if (c == '1') a.insert({i,j,k});
    }
    dist[S] = 0, q.push(S);
    
    while (not empty(q)) {
        const auto s = q.front(); q.pop();
        for (const auto &d : d6) {
            auto u = s+d;
            if (out(u) or a.count(u) or dist.count(u)) continue;
            dist[u] = dist[s]+1, q.push(u);
        }
    }
    cout << (dist.count(E) ? dist[E] : -1);
}

 

Hack을 피하자

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

이 글을 참고합시다!

 

글을 요약하자면:

• 순정 unordered_map으로는 핵 당할 위험이 있다
• 해시 함수를 정의하는데, 여기에 랜덤한 처리를 해서 핵을 피하자
• 해시 함수를 어설프게 만들어도 핵 당하기 쉽다, 좋은 해시 함수를 알아보자
• 인풋값에서 약간의 변화에도 해시값이 확확 변하는 해시 함수가 좋은 해시 함수
• Sebastiano Vigna가 디자인한.. 빠르고 안전한 splitmix64를 추천!

 

+) https://codeforces.com/blog/entry/62393?#comment-1113413 답변 대기중