SRM616D1Med ColorfulCoin

• July 22, 2016
• TopCoder

最近こういう問題見ない

問題概要(原文)

$V_i$ の価値を持つコインが $N$ 種類ある．$i<j$ において，$V_j$ が $V_i$ で割り切れることが保証される．各コインにはそれぞれ $1$ 色割り当てられているが，どんな色かは分からない．

任意の金額 $X$ を指定すると，それを達成する最小の枚数のコインが出てくるATMがある．最小何回操作すれば全てのコインの色を知ることが可能か？

考察

最大の価値を持つコインはクソでかい枚数が出せるので $1$ 回で知ることができる．

それ以外のコインについて考えよう． 簡単のため， $1,2,4,8,\ldots$ と全てのコインの，次のコインへの比率が $2$ の場合を考える．

$K$ 回操作したとき，それぞれのコインが出るかどうかは $2^K$ 通りある．全て出ないコインの色は分からない．このようにして考えると $2^K-1$ 種類のコインの色を認識することができる．

では，比率が $3$ の場合はどうなるかというと， $3^K-1$ 通りに分類することができる．

$2$ と $3$ が混在している場合はどうだろうか？ 比率が $2$ のコインの枚数を $a$ ，$3$ のコインの枚数を $b$ としたとき答えは $a \leq 2^k-1$ となるような $k$ か $a + b \leq 3^k-1$ となるような $k$ の最大値である．

このようにして，全ての比率を調べれば良い．

ソースコード

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class ColorfulCoins
{
    public int minQueries(long[] values)
    {
        var n = values.Length;
        long[] a = new long[n];
        a[n - 1] = -1;
        for (int i = 0; i < n - 1; i++)
            a[i] = values[i + 1] / values[i];
        Debug.WriteLine(string.Join(" ", a));
        var map = new SortedMap<long, int>();
        foreach (var x in a) map[x]++;
        var max = 1;
        var sum = 0;
        foreach (var kv in map)
        {
            if (kv.Key == -1) continue;
            sum += kv.Value;
            for (long i = 0, k = 1; ; i++, k *= kv.Key)
                if (k - 1 >= sum) { max = Math.Max(max, (int)i); break; }
        }
        return max;
    }


    static public T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }
}

#region HashMap
public class SortedMap<K, V>: SortedDictionary<K, V>
{
    public SortedMap() : base() { }
    new public V this[K i]
    {
        get
        {
            V v;
            return TryGetValue(i, out v) ? v : base[i] = default(V);
        }
        set { base[i] = value; }
    }
}
#endregion

コメント

• 考察が面白いmath
• いいところまで考察できたがあと一歩

• math

• Twitter
•