TopCoder SRM 616 Div1 Medium ColorfulCoins

なかなか面白い問題。
http://community.topcoder.com/stat?c=problem_statement&pm=13061

問題

コインの色と価値については先のDiv2 Mediumと同じ条件である。
TopCoder SRM 616 Div2 Medium ColorfulCoinsEasy - kmjp's blog

Div2 MediumではATM1回で色と価値の対応をつけられるか判定した。
ではATMを最少何回使えば、コインと色と価値を対応付けられるか。

解法

次の価値のコインとの比率がkであるコインがX枚あるとする。
1回ATMを使うと、各コインの登場枚数を0～(k-1)のK通りに分類できるので、1回あたり1/Kまで特定することができる。
よって、ATMをn回使えばK^n通りまでのコインを特定できそうである。
ただし実際は、各コイン最低1回は1枚以上出さないとどんな色かわからないため、n回すべて0枚の組み合わせは取れないのでK^n-1通りを特定できる。

このアイデアをもとに、以下のようにすればよい。

• 最上位を除く各コインについて次の価値のコインの比率を求める。
• 登場した各比率kについて、その比率以下のコイン枚数をX枚としたとき、k^n-1>=Xとなる最小のnを求める
• nの最大値が答え

コードにするとかなり単純。

class ColorfulCoins {
	public:
	int minQueries(vector<long long> values) {
		int N=values.size(),i;
		map<ll,int> M;
		FOR(i,N-1) M[values[i+1]/values[i]]++;
		
		int ma=1;
		ll tot=0;
		ITR(it,M) {
			ll c=it->first;
			tot+=it->second;
			ll s=1;
			int cc=0;
			while(s<=tot) s*=c,cc++;
			ma=max(ma,cc);
		}
		
		return ma;
	}
};

まとめ

本番色々紙の上で考えたけど、無事正解できてよかった。