Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/993-8597a809
この記事にトラックバックする(FC2ブログユーザー)

SRM250 DIV2 HARD - Acronyms (この記事を編集する[管理者用])

Source

TopCoder SRM250 DIV2 HARD (1000pt)
Problem Statement

問題概要

1文字の空白で区切られたものは単語.2文字の空白で区切られたものは文.
先頭が大文字から始まる単語は,大文字の部分のみ続けて読むことで文字列を圧縮する問題.
文の最初の単語は省略不可.
省略する部分は,2語以上で,最初と最後の単語は大文字で始まっていて,2個続けて大文字で始まらない単語があってはいけない.
略し方は大文字から始まる単語に含まれる大文字のみを続けて読んで,一番最後の最後についている句読点などは残す.

解法

やるだけ.
でも正直問題が曖昧でよくわからない.サンプル通るように書いたら通った.

C++による超スパゲッティなソースコード
// #includeとusing namespace std;は略

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

int next_head(string &str,int now,int ed){
  int res=now;
  while(now<ed && str[now]!=' ') now++;
  while(now<ed && str[now]==' ') now++;
  return now;
}

class Acronyms {
public:
string acronize(vector <string> document) {
  int i,j,k,m,ok,now,jump;
  int st,ed;
  string str;
  string res;

  rep(i,document.size()){
    if(i) str += " ";
    str += document[i];
  }

  st=0;
  while(st<str.size()){
    if(str[st]==' ' || str[st]=='.'){ res+=str[st]; st++; continue; }
    ed=st+1; while(ed<str.size() && (str[ed-1]!=' ' || str[ed]!=' ')) ed++;

    REP(i,st,ed){
      if(i!=st && 'A'<=str[i]&&str[i]<='Z'){
        jump=0; j=ok=i; now=1;
        for(;;){
          j=next_head(str,j,ed);
          if('A'<=str[j]&&str[j]<='Z'){ now=1; ok=j; }
          else{
            if(now==0){
              if(ok==i) break;
              ok=next_head(str,ok,ed);

              j=i;
              for(;;){
                m=next_head(str,j,ed);
                if('A'<=str[j]&&str[j]<='Z'){
                  REP(k,j,m) if('A'<=str[k]&&str[k]<='Z') res+=str[k];
                }
                j=m;
                if(j==ok) break;
              }
              
              for(m=ok-1;m>=st;m--){
                if('a'<=str[m]&&str[m]<='z') break;
                if('A'<=str[m]&&str[m]<='Z') break;
              }
              REP(k,m+1,ok) res += str[k];
              i=ok-1; jump=1; break;
            }else{
              now=0;
            }
          }
        }
        if(jump) continue;
      }
      k=next_head(str,i,ed);
      REP(j,i,k) res += str[j];
      i=k-1;
    }

    st = i;
  }

  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/993-8597a809
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。