ARC 024 C - だれじゃ

問題

C: だれじゃ - AtCoder Regular Contest 024 | AtCoder

問題概要

長さの文字列がある．この中から長さの連続する部分文字列を2つ取り出して，アナグラムになっている位置があるかどうか判定せよ．

• 
• 

アイデア

文字列内の文字はアルファベット小文字のみなので26種類になる．そして，この26種類について現れた回数の累積和を持っておくことによって文字目から始まる部分列と文字目から始まる部分列がアナグラムになっているかどうかをで判定可能になる．よってこの方法は全体での計算量となるが，これでは制約上不十分である．

さて，今答えるべきものはアナグラムになるような部分列の組が存在するか否かということであるので，文字目と文字目という情報は必要ない．そこで，この累積和の情報を文字列に起こすことにする．多くても累積和の1つの値はとなるので，「26種類に対して6桁のスペースをそれぞれ用意してそれらを全て連結したもの」を文字目から始まる部分列として表すことにしよう．例を上げれば，今見ている部分列がadbだったときには，0000010000010000000000010...0のような符号化をする．

そして，得られる全ての部分文字列を符号化した後にソートすると，隣り合っている部分が一致しているかどうかを判定することでアナグラム判定をすることができる．これで計算量はとなって，問題は解けた．また，判定の際にただ同じものが判定するだけではなく，部分文字列が文字列上でかぶっていてはいけないことに注意が必要である．

と思っていたのだが，この実装よりもそのまま累積和を利用したvectorをキーにしてソートした方が圧倒的に早かった．まあstringに変換するのムダが多いしそれはそうかと言う感じもする(stringに変換したsubmission)．こちらは1329ms要したが，以下の実装は259msで通ったし，もう少しvectorを信じよう...

実装(C++)

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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

typedef vector<int> vi;
typedef pair<vi,int> P;

int ct[100001][26]={0};

int main()
{
    int n,k;
    string s;
    cin >>n >>k >>s;

    int S=s.size();

    rep(i,S)
    {
        rep(j,26) ct[i+1][j]=ct[i][j];
        ++ct[i+1][s[i]-'a'];
    }

    vector<P> candidate;
    for(int i=k; i<=S; ++i)
    {
        vector<int> t(26);
        rep(j,26) t[j]=ct[i][j]-ct[i-k][j];
        candidate.pb( P(t,i-k) );
    }
    sort(all(candidate));

    string ans="NO";
    if(k<n)
    {
        int C=candidate.size();
        int st=0;
        for(int i=1; i<C; ++i)
        {
            if(candidate[st].fi == candidate[i].fi)
            {
                if(abs(candidate[st].se - candidate[i].se)>=k)
                {
                    ans="YES";
                    break;
                }
            }
            else st=i;
        }
    }
    cout << ans << endl;
    return 0;
}