Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Open 2010 Qual. 1A HARD - MegadiamondHunt (この記事を編集する[管理者用])

Source

TopCoder Open 2010 Algorithm Qualification Round 1A HARD (1000pt)
(Qual. 1でサーバー不調でノーゲームとなった回,問題文はArenaから見れます, ホームページには無い)

問題概要

<と>からなる50文字以下の文字列が与えられる.
<×n + >×nの文字列を取り除くとn^2点だけ得られる.
取り除く順番は自由として,得られる最高点を求める問題.

解法

ちょっと考えると,実は,対応する<と>ペアは一意に定まることが分かる.
後は,対応するペアを取り除くとき,その中にある,最も深いペアと一緒に取り除くことにする.
対応関係を見てあげて実装しても良いし,もうちょっと考えると,<×n + >×nとなっている部分をn-1以下だけ取り除くことをしなければ,最も小さいものからgreedyに取り除いていっても良い.

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 isDiamond(string dia){
  int i;
  rep(i,dia.size()/2){
    if(dia[i]!='<') return 0;
    if(dia[dia.size()-1-i]!='>') return 0;
  }
  return 1;
}

class MegadiamondHunt {
public:
int getValue(string mine) {
  int i,j,n=mine.size();
  int mx=100, st, ed;

  rep(i,n) for(j=i+1;j<n;j+=2){
    if(j-i+1 > mx) continue;
    if(!isDiamond(mine.substr(i,j-i+1))) continue;
    if(i && j+1<n && isDiamond(mine.substr(i-1,j-i+3))) continue;
    mx=j-i+1; st=i; ed=j;
  }
  if(mx==100) return 0;

  return getValue( mine.substr(0,st)+mine.substr(ed+1) ) + mx*mx/4;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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