保存されている過去のバージョンの一覧

2014年08月06日01時42分33秒

AtCoder Regular Contest #024 C問題 - だれじゃ

Source

AtCoder Regular Contest #024
問題文

問題概要

長さ $N$ のアルファベット小文字のみからなる文字列 $S$ が与えられる． $S$ の長さ $K$ の部分文字列のペアで，以下の条件1～2.をみたすものが存在するかどうかを求める問題．

  1. $2$ つの長さ $K$ の部分文字列は場所が重なっていない
  2. $2$ つの長さ $K$ の部分文字列はアナグラムになっている．つまり全ての文字について，$2$ つの部分文字列に含まれるその文字の数は等しい

解法

アナグラムの時は等しくなるようなローリングハッシュっぽいものを用いる．
例えば，各文字 $k$ に乱数 $R_k$ を割り振る．
また，$S$ の $k$ 文字目までに出てくる文字に割り振られた乱数の累積和 $H_k = R_{S_1} + R_{S_2} + \ldots R_{S_k}$ を計算しておく．
すると，$A_x := H_{x+K}-H_{x} = H_{y+K}-H_{y} =: A_y$ の時，$S$ の $x$ 文字目から始まる長さ $K$ の部分文字列と，$y$ 文字目から始まる長さ $K$ の部分文字列はアナグラムになっている．
$A_{K+1}, A_{K+2}, \ldots$ をハッシュに突っ込んでおき，$A_1$ と同じものがハッシュ内に存在するか調べる．
存在しなければ，$A_{K+1}$ をハッシュ内から消し，$A_2$ と同じものがハッシュ内に存在するか調べる，としていく．
時間計算量は $O(N)$．

C++によるスパゲッティなソースコード

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

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long
#define ull unsigned ll

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}return s;}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}

template<class T>
struct ullHash{
  ull *key; T *val; unsigned memory, size, mask;

  void clear(){memset(val,0,size*sizeof(T));}
  void clear(int sz){size=1;while(size<sz)size*=2;mask=size-1;clear();}
  void init(int mem, int sz){memory=mem;size=1;while(size<sz)size*=2;mask=size-1;if(memory<size)memory=size;key=(ull*)malloc(memory*sizeof(ull));val=(T*)malloc(memory*sizeof(T));if(size)clear();}
  int function(ull a){return (a*97531)&mask;}
  T get(ull a){int i=function(a);for(;key[i]!=a&&val[i]!=0;)i=(i+1)&mask;if(key[i]!=a) return 0;return val[i];}
  void set(ull a, T v){int i=function(a);for(;key[i]!=a&&val[i]!=0;)i=(i+1)&mask;key[i]=a;val[i]=v;}
  T increase(ull a, T v = 1){int i=function(a);for(;key[i]!=a&&val[i]!=0;)i=(i+1)&mask;key[i]=a;return val[i]+=v;}
};


int N, K;
char S[110000];

#define D 9999773

ull val[300];
ull hh[110000];

int main(){
  int i, j, x, res = 0;
  ullHash<int> hash;

  val[0] = 1;
  REP(i,1,300) val[i] = val[i-1] * D;
  
  reader(&N, &K);
  reader(S);

  hash.init(200000, 200000);

  hh[0] = 0;
  rep(i,K) hh[0] += val[S[i]];
  REP(i,K,N) hh[i-K+1] = hh[i-K] + val[S[i]] - val[S[i-K]];

  REP(i,K,N-K+1) hash.increase(hh[i]);
  REP(i,K,N-K+1){
    x = hash.get(hh[i-K]);
    if(x/100 < x%100) res = 1;
    hash.increase(hh[i], 100);
  }

  if(res) writer("YES\n"); else writer("NO\n");

  return 0;
}

Current time: 2024年04月19日06時01分52秒
Last modified: 2014年08月06日01時42分33秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Regular_Contest ARC024 ARC_C
トップページに戻る

Logged in as: unknown user (not login)

ログイン：