Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

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

問題概要

AとBからなる文字列で,
 文字Xは合計でcountX文字以下
 連続するXはmaxX文字以下
を満たす最大の文字列の長さを求める問題.
countA, countB, maxA, maxBはそれぞれ0以上10^6以下.

解法

maxA, maxBが0の時は例外処理しておくのが無難.
後は,使える数が小さい方を区切りとして,使える数が大きい方を全部消費できるかどうか,消費できないなら最大どれだけ消費できるかを求めるやる.
以下のコードの方針は,使える数が大きい方から,もう片方の残り文字数を1より大きく下回らない範囲で使えるだけ使ってやるというgreedy解法.

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

class BeautifulString {
public:
int maximumLength(int countA, int countB, int maxA, int maxB) {
  int use,res=0;

  if(maxA==0) return min(countB, maxB);
  if(maxB==0) return min(countA, maxA);

  if(countA < countB) swap(countA,countB), swap(maxA,maxB);
  while(countA){
    use = maxA;
    if(countA - use < max(0,countB-1)) use = countA - max(0,countB-1);
    if(use<=0) use=1;
    if(countA-use < 0) break;
    res += use; countA -= use;
    swap(countA,countB), swap(maxA,maxB);
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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