Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Open 2011 Algorithm Qual. 3 MEDIUM - CoinMachinesGame (この記事を編集する[管理者用])

Source

TopCoder Open 2011 Algorithm Qualification Round 3 MEDIUM (500pt)
Problem Statement
TopCoderニコ生オープン TCO11 Qual. 3 自分の参加記録

問題概要

アーケードゲーム機がN個 (50以下) ある.
最初コインをC個 (10^9以下) 持っている.
それぞれのアーケードゲームをプレイするに当たって,最初に必要なコインの数,最後に帰ってくるコインの数が与えられる.
帰ってくるコインの数は,最初に必要なコインの数より厳密に小さい.
同じゲーム機を何回もプレイして良いので,最大で何回ゲームをプレイ出来るかを求める問題.

解法

プレイできるゲームの中で,賞味の消費コイン (必要コイン-帰ってくるコイン) が少ない方からプレイすれば良い.
単純に,1回プレイごとにシミュレーションするとTLEになるので,プレイできる回数を求めて,一気に処理する.

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

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

void intIntSort(int d[],int m[],int s){int i=-1,j=s,k,t; if(s<=1)return;k=(d[0]+d[s-1])/2;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;t=m[i];m[i]=m[j];m[j]=t;}intIntSort(d,m,i);intIntSort(d+j+1,m+j+1,s-j-1);}

class CoinMachinesGame {
public:
int maxGames(int coins, vector <int> need, vector <int> give) {
  int i,j,k,kk,n,usable;
  int use[50], val[50], ind[50], plays;
  int res = 0;
  
  n = need.size();
  rep(i,n) val[i] = use[i] = need[i] - give[i];
  rep(i,n) ind[i] = i;
  intIntSort(val,ind,n);

  rep(kk,n){
    k = ind[kk];
    usable = coins - need[k];

    plays = (usable + use[k]) / use[k];
    if(plays <= 0) continue;

    res += plays;
    coins -= use[k] * plays;
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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