[ICPC] 백준 10266 - 시계 사진들

https://www.acmicpc.net/problem/10266

스텝 1 - 수열 정렬

시계 바늘은 모두 똑같이 생겼다. 따라서 주어진 각들을 오름차순으로 정렬해도 시계의 위상은 유지된다. 그러니까 일단 정렬하자.

스텝 2 - 각도값 보정

두 수열에 대해 맨 처음의 값이 0이 되도록 모든 원소에 적절한 값을 빼준다. 그래도 위상은 유지된다.

스텝 3 - 둘 중 하나를 두 배 하고 스트링 매칭

예제 입력 2를 보면 정렬을 함에도 절대적인 각도가 차이가 있는데 이를 해소하기 위해 수열을 복제하는 테크닉을 쓰면 정상적인 스트링 매칭이 가능하다.

 

이제 스트링 매치를 해서 매칭이 되면 possible, 그렇지 않으면 impossible을 출력하면 된다.

 

전체 코드 - kmp로 매칭했다.

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
vector<int> bake_pi(vector<int> &pat) {
  int sz = pat.size();
  vector<int> ret(sz);
 
  int j = 0;
  for (int i = 1; i < sz; i++) {
    while (j and pat[i] != pat[j]) j = ret[j - 1];
    if (pat[j] == pat[i]) ret[i] = ++j;
  }
 
  return ret;
}
 
vector<int> kmp(vector<int> &target, vector<int> &pat) {
  vector<int> ret;
  auto pi = bake_pi(pat);
 
  int j = 0;
  for (int i = 0; i < target.size(); i++) {
    while (j and target[i] != pat[j]) j = pi[j - 1];
    if (target[i] != pat[j]) continue;
    if (j == pat.size() - 1) {
      ret.push_back(i - j);
      j = pi[j];
    } else {
      ++j;
    }
  }
  return ret;
}
 
int n;
vector<int> c1;
vector<int> c2;
 
void solve()
{
  cin >> n;
  c1.resize(n);
  c2.resize(n);
  for (int &i : c1) cin >> i;
  for (int &i : c2) cin >> i;
  int mn = *min_element(c1.begin(), c1.end());
  for (int &i : c1) i -= mn;
  mn = *min_element(c2.begin(), c2.end());
  for (int &i : c2) i -= mn;
  sort(c1.begin(), c1.end());
  sort(c2.begin(), c2.end());
  c1.push_back(360000);
  c2.push_back(360000);
 
  vector<int> c3, c4;
  for (int i = 0; i < n; i++)
  {
    c3.push_back(c1[i + 1] - c1[i]);
    c4.push_back(c2[i + 1] - c2[i]);
  }
  int sz = c4.size();
  for (int i = 0; i < sz; i++) c4.push_back(c4[i]);
 
  auto ans = kmp(c4, c3);
 
  cout << (ans.size() ? "possible" : "impossible");
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록