Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM394 DIV1 EASY/DIV2 MEDIUM - RoughStrings (この記事を編集する[管理者用])

Source

TopCoder SRM394 DIV1 EASY (250pt)
TopCoder SRM394 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

アルファベット小文字のみからなる長さK (50以下) の文字列が与えられる.
n文字 (K-1以下) 以下だけ消して,ラフネスを最小化したい.最小値を求める問題.
ラフネスとは,文字列に最も多く現れる文字の文字数 - 文字列に最も少なく(ただし1文字以上)現れる文字の文字数.

解法

最も多い文字の文字数MAXと,最も少ない文字の文字数MINを決め付ける.
それが可能かどうかは,各文字に対して,MAXより多ければMAXになるまで消す,MINより小さければ全てなくなるまで消す,として,n回の削除で実行可能かどうかを判定する.
使う文字をgreedyに全探索して,残りは多い文字から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)

class RoughStrings {
public:
int minRoughness(string s, int n) {
  int i,x,y,use;
  int in[26]={};
  int res=1000;

  rep(i,s.size()) in[s[i]-'a']++;
  rep(x,s.size()+1) REP(y,x,s.size()+1){
    if(y-x >= res) continue;
    use = 0;
    rep(i,26){
      if(in[i] > y) use += in[i]-y;
      if(in[i] < x) use += in[i];
    }
    if(use <= n) res = y-x;
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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