Codeforces Round #557 (Div. 1) B. Chladni Figure (R1900)

KMP 法で殴ったけど、愚直にやっても調和級数的計算量で間に合うね。

• 問題へのリンク

問題概要

円周上に等間隔に 個の点が打たれている。これらの点を端点とした 個の線分がある (下図のような感じ)。

これが回転対象性をもつかどうかを判定せよ (1 周未満の回転で模様が一致するかを判定せよ)。

制約

• 
• 

考えたこと

なんとなく文字列のように扱えそうな気がした。具体的には

• vec[v] ← 点 から見て隣接している頂点への差分の集合

とする (vector<vector<int>> 型などで管理)。これを、各文字が vector<int> 型であるような文字列とみなすと、KMP 法が使える。KMP 法を用いると、文字列の最小周期 が求められる。 かつ であれば "Yes"、そうでなければ "No"。これで計算量は となる。

なお、KMP 法を使わなくても、周期 を愚直に試しても OK。これで計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;

// T = string or vector<long long>
template<class T> struct KMP {
    T pat;
    vector<int> fail;

    // construct
    KMP(const T &p) { init(p); }
    void init(const T &p) {
        pat = p;
        int m = (int)pat.size();
        fail.assign(m+1, -1);
        for (int i = 0, j = -1; i < m; ++i) {
            while (j >= 0 && pat[i] != pat[j]) j = fail[j];
            fail[i+1] = ++j;
        }
    }

    // the period of S[0:i]
    int period(int i) { return i - fail[i]; }
    
    // the index i such that S[i:] has the exact prefix p
    vector<int> match(const T &S) {
        int n = (int)S.size(), m = (int)pat.size();
        vector<int> res;
        for (int i = 0, k = 0; i < n; ++i) {
            while (k >= 0 && S[i] != pat[k]) k = fail[k];
            ++k;
            if (k >= m) res.push_back(i - m + 1), k = fail[k];
        }
        return res;
    }
};

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> X(M), Y(M);
    for (int i = 0; i < M; ++i) {
        cin >> X[i] >> Y[i];
        --X[i], --Y[i];
    }
    vector<vector<int>> str(N);
    for (int i = 0; i < M; ++i) {
        str[X[i]].push_back( (Y[i]-X[i]+N) % N );
        str[Y[i]].push_back( (X[i]-Y[i]+N) % N );
    }
    for (int i = 0; i < N; ++i) sort(str[i].begin(), str[i].end());
  
    KMP<vector<vector<int>>> kmp(str);
    int syu = kmp.period(N);
    if (syu < N && N % syu == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}