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

2014年12月05日01時34分27秒

yukicoder No.52 - よくある文字列の問題

Source

ニコニコミュニティ
問題文

問題概要

アルファベット小文字からなる文字列 $S$ が与えられる．
最初，文字列 $T$ を空として，$S$ の文字数が正であるかぎり以下の処理を行う．
処理: $S$ の先頭，または，最後の文字を取り除き，取り除いた文字を $T$ の末尾に加える．
最終的に，文字列 $T$ としてあり得る文字列は何通りあるかを求める問題．

解法

左右どちらから取るかを文字数の回数分だけ選べば，$T$ は確定する．
これは $2^{|S|}$ パターンしか無いので，全部試せば良い．
後は，$T$ をソートするなり，$\verb|set|$ に突っ込むなりして，異なるものを数えれば良い．
時間計算量は，工夫すれば $O(2^{|S|})$ 程度，愚直にやっても $O(|S|^2 2^{|S|})$ 程度．

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)

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;}c[s]='\0';return s;}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}

int main(){
  int i, j, k, N;
  int a,b;
  char in[100];
  set<string> s;

  N = reader(in);
  rep(i,1<<N){
    string str;
    a = 0; b = N-1;
    rep(j,N){
      if(i&1<<j) str += in[a++];
      else       str += in[b--];
    }
    s.insert(str);
  }
  writer((int)s.size(),'\n');

  return 0;
}

Current time: 2024年04月26日05時19分31秒
Last modified: 2014年12月05日01時34分27秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン：