Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM504.5 DIV1 MEDIUM - TheJackpotDivOne (この記事を編集する[管理者用])

Source

TopCoder SRM504.5 DIV1 MEDIUM (550pt)
Problem Statement
SRM504.5 DIV1 自分の参加記録

問題概要

N人 (47以下) の所持金 (それぞれ10^18以下) が与えられる.
自分の所持金M (10^18)も与えられる.
以下の操作を自分の所持金が尽きるまで繰り返したとき,N人の所持金をソートして返す問題.
 現在のN人の所持金の平均値より大きい最小の整数をZとする
 N人の中で最も所持金の少ない人が,所持金Zになるか,自分の所持金が尽きるまで渡す

解法

全員の所持金が等しくなったら,後は,1ずつ分配していくのだから,等しく分配すれば良い.
それまでのステップ数は実はたかだか3~4万ステップ程度なのでシミュレーションできる.

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

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

#define ll long long

class TheJackpotDivOne {
public:
vector<ll> find(vector<ll> in, ll rest) {
  int i,j,k,n;
  int step = 0;
  ll mean, md, add;

  n = in.size();

  while(rest){
    sort(in.begin(), in.end());
    step++;
    if(in[0]==in[n-1]){
      add = rest / n;
      rep(i,n) in[i] += add, rest -= add;
    }
    
    mean = md = 0;
    rep(i,n){
      mean += in[i] / n;
      md   += in[i] % n;
    }
    mean += md / n;

    add = mean+1 - in[0];
    if(rest < add) add = rest;
    in[0] += add; rest -= add;
  }

  printf("%d\n",step);
  sort(in.begin(), in.end());
  return in;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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