SRM616D1Med ColorfulCoin

最近こういう問題見ない

問題概要(原文)

$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
  • いいところまで考察できたがあと一歩