Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Open 2010 Qual. 2 EASY - JingleRingle (この記事を編集する[管理者用])

Source

TopCoder Open 2010 Algorithm Qualification Round 2 EASY (250pt)
Problem Statement
TopCoderニコ生オープン 第1回 自分の参加記録

問題概要

オンラインゲームで品物の売り買いを行います.
販売が成立すると,
 売り手は,買い手からお金を受け取って,売り手は,受け取ったお金のtax% (切り捨て)を政府に支払わなければいけない.
 また,買い手は売り手から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)

class JingleRingle {
public:
int profit(vector <int> buy, vector <int> sell, int tax) {
  int i,k,res=0;

  sort(buy.rbegin(),buy.rend());
  sort(sell.begin(),sell.end());

  rep(i,min(buy.size(),sell.size())){
    k = buy[i] - (buy[i]*tax)/100 - sell[i];
    if(k>0) res+=k;
  }

  return res;
}

};

以下はTopCoderニコ生Open本番中にサブミットしたコード.

// #includeとusing namespace std;は略

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

class JingleRingle {
public:
int profit(vector <int> buy, vector <int> sell, int tax) {
  int i,j,k;
  int res=0;

  sort(buy.rbegin(),buy.rend());
  sort(sell.begin(),sell.end());

  rep(i,min(buy.size(),sell.size())){
    k = buy[i];
    k -= (k*tax)/100;
    k -= sell[i];
    if(k>0) res+=k;
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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