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: 2017年09月25日11時36分37秒
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)

ログイン: