SRM616 Div1 Medium "ColorfulCoins"

問題

TopCoder Statistics - Problem Statement

訳

カラーランドにおける通貨は様々な種類のコインによって成り立っている。コインの額面には次の３つのルールがある。

1. 額面は一意の正の整数である。
2. 1円のコインが必ずある。
3. 額面が違うコインのペアは、必ず割り切れるようになっている。

あなたはカラーランドにあるコインの全ての額面を昇順に並べたlong[] valuesが与えられる。

異なる額面のコインを見分ける方法は、それに塗られた色によってのみである。カラーランドにある各コインは一色の色で塗られており、次のような単純なルールがある。

同じ額面のコインは同じ色で塗られている。
違う額面の２つのコインが同じ色で塗られていることはない。

あなたは額面の全ての種類を知っていはいたが、それぞれがどんな色で塗られているかは知らなかった。また、どのような色が使われているかも知らないでいる。

あなたはそれぞれの額面にどんな色が使われているか知りたくなった。それを成し遂げるため、無限大の額が使えるキャッシュカードを使用することにする。あとは無限大のお金を引き出せるATMを操作する。１回の操作ではATMから何円引き出すかを指定することができる。ATMは指定された金額を払いだす。あなたは、ATMがコインの数がなるべく少なくなるように払い出す事を知っている。(このルールにより、払いだされるコインの種類とその数は一意に決定されることに注意して欲しい）

あなたが全ての額面と、その色を認識するために、最小何回ATMを操作すればよいかを返せ。

制約

1 <= values.size() <= 60
1 <= values[i] <= 10^18
values[0] == 1

考えたこと（１日以上・・・）

ATMからめちゃくちゃ大きな金額を引き落とせば、一番高いコインをたくさん出せるため、一番でかい額面のコインはすぐ判断できる。1円～２番目に高いコインは一度に出せる数に制限がある。1円、3円、6円とあったら、1円は2枚しか出せないし、3円は1枚しか出せない。ATMがコインの枚数を最小化するためである。操作の特徴はこんな感じ。

まずは{1, 2, 4, 8, 16, 32...} と全て1枚しか出せない場合を考えてみる。最も効率よく見分ける方法は、２分木的に出す出さないを繰り返すといい。どういうことかというと、下の図のようにそれぞれの額面を葉に見立てて２分木を作って、左の子は出さない、右の子は出す、みたいにやる。

すると、
「出ない・出た・出ない」←これ４円玉だな
「出る・出る・出ない」←これ６４円玉だな
となり、８種類を３回で見分けることができる。

実際には全ての色を１回は出さなくてはいけないので、「出ない・出ない・出ない」のパターンを除いて７種類見分けることができる。このやり方なら「全てのコインが１枚しか出せない・６０種類」という最悪のパターンでも[60 < 2^6-1 = 63]なので最大６回操作を行えばよいことになる。

問題ではコインは１枚出せたり２枚・５枚と出せる場合もあり、それが混在している。これをどうするか・・。例えば２枚だせるコインは０枚出す・１枚出す・２枚出すの３パターン使えるため、N回の操作でN^3-1種類見分けることができる。ここは操作回数を２回に固定して考えてみる。

全てのコインが２枚だせると仮定すると、下の図のように２回の操作で3^2-1 = 8種類のコインを見分けることが可能。

ちょっと観察すると、１枚しかだせないコインがあったとしても、ここに潜り込ませられることが分かる。矢印で示すコインは判別するのに１枚のコインしか使っていないため、２回の操作だと１枚しか出せないコインを３種類までなら判別することができるのだ。

同様に、２回の操作だと２枚まで出せるコインを７枚まで判別することができ、３枚まで出せるコインだと１５枚（2^4-1)まで判別可能となる。

まとめると、２回の操作で全てのコインを判別できるかは、

１枚まで出せるコイン・・・・・３種類まで
１～２枚まで出せるコイン・・・７種類まで
１～３枚まで出せるコイン・・・１５種類まで
１～４枚まで出せるコイン・・・３１種類まで
。。。

これらを全て満たせばよいことになる。

これを１回～６回の操作までで判断してやれば答えとなる。

事後

この問題・・・・好きかも（ポッ

ソースコード

class ColorfulCoins {

    public:

    int minQueries(vector<long long> values) {
        vector<long long> num;

        // コインの出せる枚数の昇順を取得する
        for (int i = 1; i < values.size(); i++) {
            num.push_back(values[i] / values[i - 1] - 1);
        }
        sort(num.begin(), num.end());

        int n = num.size();

        // １枚だったらやらんでよし
        if (n == 0) return 1;

        // １～５回の操作回数を試す
        for (int ope = 1; ope <= 5; ope++) {
            bool ok = true;
            // 出せるコイン枚数で試す
            // 1～b-1枚出せるコインはmax枚以下でなければならない
            for (int b = 2; b <= 60; b++) {
                int max = pow(b, ope) - 1; 
                int count = 0;
                for (int i = 0; i < n; i++) {
                    if (num[i] <= b - 1) {
                        count++;
                    }
                }
                if (max < count){
                    ok = false;
                }
            }

            if (ok) {
                return ope;
            }
        }

        // 操作回数は最大でも６回
        return 6;
    }
};