BOJ 10266

백준 10266, Rolling Hash

오랜만에 정답을 보지 않고 맞춘 문제다.

두 시계의 시계 바늘들의 간격이 똑같다면 한 쪽 시계를 돌려서 다른 한 쪽에 맞출 수 있다.

시계 바늘들의 간격을 일종의 문자열로 생각해서 rolling hash를 적용하면 쉽게 풀 수 있다.

정렬에 $O(NlogN)$, 최대 $M = 360000$ 번 돌려가며 비교하고, 각 비교는 $O(1)$ 이라서 넉넉하게 풀린다.

보통은 KMP를 적용해서 푸는듯 하다. 바늘들의 간격을 문자열로 생각하는게 요점인 문제.

Source Code

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

#define ll long long

#define pii pair<int, int>
#define pll pair<ll, ll>
#define MAXI 1000000000
#define cplx complex<double>
#define MOD 9901
const double PI = acos(-1);
const ll INF = INT_MAX / 4;

using namespace std;

vector<ll> clock1, clock2;
deque<ll> diff1, diff2;
int N;
ll P = 360007;
ll M = 1e9 + 9;
ll modp_list[200001];

ll compute_initial_hash(const deque<ll>& diff) {
    ll hash_value = 0;
    ll p_pow = 1;
    for (int i = 0; i < N; ++i) {
        hash_value = (hash_value + ((diff[i]) * p_pow) %M) % M;
        p_pow = (p_pow * P) % M;
    }
    return hash_value;
}

ll push_hash_right(deque<ll>& diff, ll previous_hash){
    ll last_diff = diff[N - 1];
    diff.pop_back();
    diff.push_front(last_diff);
    ll pushed_hash = 0;
    pushed_hash = (((P * previous_hash) % M) + last_diff) % M;
    pushed_hash -= (last_diff * modp_list[N]) % M;
    if (pushed_hash < 0) pushed_hash += M;
    return pushed_hash;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;

    for (int i = 0; i < N;++i){
        ll tmp;
        cin >> tmp;
        clock1.push_back(tmp);
    }
    for (int i = 0; i < N; ++i) {
        ll tmp;
        cin >> tmp;
        clock2.push_back(tmp);
    }

    modp_list[0] = 1;
    for (int i = 1; i < 200001;++i){
        modp_list[i] = (modp_list[i - 1] * P) % M;
    }

    sort(clock1.begin(), clock1.end(), less<ll>());
    sort(clock2.begin(), clock2.end(), less<ll>());

    for (int i = 1;i<N;++i){
        diff1.push_back(clock1[i] - clock1[i - 1]);
        diff2.push_back(clock2[i] - clock2[i - 1]);
    }
    diff1.push_back(360000 - clock1[N-1] + clock1[0]);
    diff2.push_back(360000 - clock2[N-1] + clock2[0]);
    // cout <<  modp_list[N] << "\n";

    // ll starting_hash1 = compute_initial_hash(diff1);
    // cout << "hash1: " << starting_hash1 << "\n";
    // for (int i = 0; i < N; ++i) {
    //     cout << diff1[i] << " ";
    // }
    // cout << "\n";
    // ll pushed_hash = push_hash_right(diff1, starting_hash1);
    // cout << "pushed: " << pushed_hash << "\n";
    // for (int i = 0; i < N;++i){
    //     cout << diff1[i] << " ";
    // }

    ll hash1 = compute_initial_hash(diff1);
    ll hash2 = compute_initial_hash(diff2);
    bool hash_match = false;
    for (int i = 0; i <= N;++i){
        // cout << "hash2: " << hash2 << "\n";
        if(hash1 == hash2){
            hash_match = true;
            break;
        }
        ll new_hash2 = push_hash_right(diff2, hash2);
        hash2 = new_hash2;
    }

    if (hash_match == true)
        cout << "possible";
    else
        cout << "impossible";

    return 0;
}

/*
//https://www.acmicpc.net/source/16420570
//solution from hellogaon, using KMP

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int INF = 987654321;
const int MOD = 1000000007;

vector<int> getpi(string& N){
  int n = N.size();
  vector<int> pi(n, 0);
  for(int i=1,j=0;i<n;i++){
    while(j > 0 && N[i] != N[j]) j = pi[j-1];
    if(N[i] == N[j]) pi[i] = ++j;
  }
  return pi;
}

vector<int> kmp(string& M, string& N){
  int m = M.size(), n = N.size();
  vector<int> ret, pi = getpi(N);
  for(int i=0,j=0;i<m;i++){
    while(j > 0 && M[i] != N[j]) j = pi[j-1];
    if(M[i] == N[j]){
      ++j;
      if(j == n){
        ret.pb(i-n+1); j = pi[j-1];
      }
    }
  }
  return ret;
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  string s(360000, '0'), t(360000, '0');
  int N; cin >> N;
  for(int i=0;i<N;i++){
    int X; cin >> X;
    s[X] = '1';
  }
  for(int i=0;i<N;i++){
    int X; cin >> X;
    t[X] = '1';
  }
  s += s;
  vector<int> ret = kmp(s, t);
  if(ret.size()) cout << "possible\n";
  else cout << "impossible\n";
}


*/

PREVIOUSBOJ 1605