TopCoder SRM616 DIV1 MEDIUM - ColorfulCoins

Source

TopCoder SRM616 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

この国では，$N$ 種類の硬貨を使用しており，$i$ 番目の硬貨の価値は $V_i$ 円である．
ここで，任意の $i$ について，$V_i$ は $V_{i-1}$の倍数となっていて，$V_i$ はすべて異なる．また，$V_1=1$．
硬貨は，それぞれ違う色をしているのだが，どの硬貨がどんな色か知らず，全体として使われている色の集合も知らない．
銀行で，お金を引き出すと，そのお金ぴったりになるような，最小枚数の硬貨が出てくることがわかっている．
最小で，何回お金を引き出せば，全ての硬貨を判別し，全ての硬貨の色を知ることができるかを求める問題．
お金の額は問わず，無限に引き出せる．

解法

$1$ 回の引き出しで $V_N$ の硬貨はいくらでも引き出せるが，$k < N$ に対して $V_k$ の硬貨は $V_{k+1} / V_k$ 枚未満しか出てこない．
ただ，それさえ満たせば，任意の枚数を出すようにできる．
そこで，それぞれの硬貨が何通りの出し方があるか $M_k = V_{k+1} / V_k$ を使って考える．（$0$ 枚から $M_k-1$ 枚の $M_k$ 通り）
何通りの出し方があるものがボトルネックになるかを全部調べる．
つまり，$k$ を $2$ から順番に増やしながら，出し方が $k$ 通り以下のコインの枚数を数えて，
それだけの枚数のコインが，全部 $k$ 通りの出し方があるとした時の，それらのコインの色を知るための最小回数を求める．
$k$ を動かして，その最小回数の最大値が答えとなる．
$1$ 回の引き出しで，$k$ 通りの引き出し方ができるので，$n$ 回引き出せば，$k^n$ コインまでなら区別できる．
が，色を知らなくてはいけないので，全ての引き出しにおいて，$0$ 枚引き出す，という選択はできない．
そこで，$k^n -1$ 枚までなら色を知った上で区別することができる．

C++によるスパゲッティなソースコード

// #includeなどは略しています
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

int trial(int coins, int k){
  int res = 0;
  coins++;
  while(coins>1){
    coins = (coins + k - 1) / k;
    res++;
  }
  return res;
}

class ColorfulCoins {
public:
int minQueries(vector<ll> values) {
  int i, k, n;
  ll in[90];
  int res, coins;

  n = values.size() - 1;
  if(n==1) return 1;

  rep(i,n) in[i] = values[i+1] / values[i];

  res = 1;
  REP(k,2,n+1){
    coins = 0;
    rep(i,n) if(in[i] <= k) coins++;
    res = max(res, trial(coins, k));
  }

  return res;
}

}

Current time: 2024年04月20日00時26分21秒
Last modified: 2014年04月11日05時29分32秒 (by laycrs)
Tags: Competitive_Programming TopCoder Single_Round_Match SRM616 SRM_Div1_Medium
トップページに戻る

Logged in as: unknown user (not login)

ログイン：