Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM499 DIV1 EASY (250pt)
TopCoder SRM499 DIV2 MEDIUM (500pt)
Problem Statement
SRM499 DIV1 自分の参加記録

問題概要

N匹 (50以下) の同じ街に住むウサギに,
 あなたの街に,あなた以外に,あなたと同じ色のウサギは何人いますか?
と聞いた答えa[k]が (1000000以下) 与えられる.
答えが正しいと仮定したとき,その街に住むウサギの最小数を求める問題.

解法

同じ答えのウサギをまとめる.
そのグループから 答え+1 匹までは同じ色にできるので同じ色にしていく.
後は,同じ色の組それぞれに対して, 答え+1 匹のウサギがいるはずなので,それを足していく.

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

class ColorfulRabbits {
public:
int getMinimum(vector <int> in) {
  int i,st,ed;
  int res = 0;

  sort(in.begin(), in.end());

  for(i=0;i<in.size();){
    st = ed = i;
    while(ed < in.size() && in[ed]==in[st]) ed++;

    while(st<ed){
      res += in[st]+1;
      st += in[st]+1;
    }

    i = ed;
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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