ARC024 C-だれじゃ
【問題】
arc024.contest.atcoder.jp
【考察】
そこまで難しくないんですが、結構一般的な知見を得た問題。
以下簡単のため、互いに共通部分をもっていてもアナグラムダジャレになれる、と考えます。まず、2 つの部分文字列がアナグラムの関係にあるとき、その部分列の各アルファベットの出現回数は等しくなります。そこで、ある英小文字列に含まれる 'a' ~ 'z' の数を記録しておく配列を便宜的にその文字列の「頻度表」と呼ぶことにすれば、S の長さ K の部分文字列を調べ上げ、同じ「頻度表」をもつものが見つかったなら S は長さ K のアナグラムダジャレを含むことが分かります。二分探索木を使って見たことのある部分文字列の頻度表を入れていけば、これを判定することができます。
当たり前ですが、全ての部分文字列の頻度表を愚直に作り上げていこうとすると、O(N^2) となり TLE してしまいます。ではどうすればいいかというと、ある部分文字列の頻度表は、すぐ隣の部分文字列の頻度表から O(1) で構成できる事実を用います。というのも、区間から消えるアルファベットを頻度表から減じ、新しく区間に入るアルファベットを頻度表に増やせばいいからです。この性質を利用することで、全ての頻度表を O(N) で列挙することができます。
以上をまとめます。区間の固定長 K の部分区間を調べ上げるような問題を考えます。これは愚直にやろうとすると、区間の大きさの二乗に比例する計算量がかかってしまいます。しかし、ある部分区間の情報が、その隣の部分区間の情報から O(1) で構成できるような性質をもっているときは、左から順に走査していくことで区間の大きさに比例する計算量で調べ上げることができます。
自明と言えば自明なことですが、意識しておけば若干閃きやすくなるような気がする。あと実装が地味にややこしいので、慣れておくとよい気がする。
あとこの問題、アナグラムダジャレがあるかないかだけじゃなくて、アナグラムダジャレの関係になるような組の数も、同じ計算量で求められます。
【コード】
int main() { ios::sync_with_stdio(false); int n,k; cin>>n>>k; string s; cin>>s; map<vector<int>, int> ma; vector<int> c(26,0); REP(i,k-1) { c[s[i]-'a']++; } bool f=false; FOR(i,k-1,n) { c[s[i]-'a']++; if(ma.count(c)!=0&&ma[c]<=i-(2*k-1)) f=true; if(ma.count(c)==0) ma[c]=(int)(i-(k-1)); c[s[i-(k-1)]-'a']--; } if(f) cout<<"YES"<<endl; else cout<<"NO"<<endl; }
【使ったアイデア】
固定長の部分区間を調べ上げるテクニック。
【得た知見】
以上の一般化。
