SRM616 Div1 Medium "ColorfulCoins"
問題
TopCoder Statistics - Problem Statement
訳
カラーランドにおける通貨は様々な種類のコインによって成り立っている。コインの額面には次の3つのルールがある。
1. 額面は一意の正の整数である。 2. 1円のコインが必ずある。 3. 額面が違うコインのペアは、必ず割り切れるようになっている。
あなたはカラーランドにあるコインの全ての額面を昇順に並べたlong[] valuesが与えられる。
異なる額面のコインを見分ける方法は、それに塗られた色によってのみである。カラーランドにある各コインは一色の色で塗られており、次のような単純なルールがある。
同じ額面のコインは同じ色で塗られている。 違う額面の2つのコインが同じ色で塗られていることはない。
あなたは額面の全ての種類を知っていはいたが、それぞれがどんな色で塗られているかは知らなかった。また、どのような色が使われているかも知らないでいる。
あなたはそれぞれの額面にどんな色が使われているか知りたくなった。それを成し遂げるため、無限大の額が使えるキャッシュカードを使用することにする。あとは無限大のお金を引き出せるATMを操作する。1回の操作ではATMから何円引き出すかを指定することができる。ATMは指定された金額を払いだす。あなたは、ATMがコインの数がなるべく少なくなるように払い出す事を知っている。(このルールにより、払いだされるコインの種類とその数は一意に決定されることに注意して欲しい)
あなたが全ての額面と、その色を認識するために、最小何回ATMを操作すればよいかを返せ。
制約
1 <= values.size() <= 60
1 <= values[i] <= 10^18
values[0] == 1
考えたこと(1日以上・・・)
ATMからめちゃくちゃ大きな金額を引き落とせば、一番高いコインをたくさん出せるため、一番でかい額面のコインはすぐ判断できる。1円~2番目に高いコインは一度に出せる数に制限がある。1円、3円、6円とあったら、1円は2枚しか出せないし、3円は1枚しか出せない。ATMがコインの枚数を最小化するためである。操作の特徴はこんな感じ。
まずは{1, 2, 4, 8, 16, 32...} と全て1枚しか出せない場合を考えてみる。最も効率よく見分ける方法は、2分木的に出す出さないを繰り返すといい。どういうことかというと、下の図のようにそれぞれの額面を葉に見立てて2分木を作って、左の子は出さない、右の子は出す、みたいにやる。
すると、
「出ない・出た・出ない」←これ4円玉だな
「出る・出る・出ない」←これ64円玉だな
となり、8種類を3回で見分けることができる。
実際には全ての色を1回は出さなくてはいけないので、「出ない・出ない・出ない」のパターンを除いて7種類見分けることができる。このやり方なら「全てのコインが1枚しか出せない・60種類」という最悪のパターンでも[60 < 2^6-1 = 63]なので最大6回操作を行えばよいことになる。
問題ではコインは1枚出せたり2枚・5枚と出せる場合もあり、それが混在している。これをどうするか・・。例えば2枚だせるコインは0枚出す・1枚出す・2枚出すの3パターン使えるため、N回の操作でN^3-1種類見分けることができる。ここは操作回数を2回に固定して考えてみる。
全てのコインが2枚だせると仮定すると、下の図のように2回の操作で3^2-1 = 8種類のコインを見分けることが可能。
ちょっと観察すると、1枚しかだせないコインがあったとしても、ここに潜り込ませられることが分かる。矢印で示すコインは判別するのに1枚のコインしか使っていないため、2回の操作だと1枚しか出せないコインを3種類までなら判別することができるのだ。
同様に、2回の操作だと2枚まで出せるコインを7枚まで判別することができ、3枚まで出せるコインだと15枚(2^4-1)まで判別可能となる。
まとめると、2回の操作で全てのコインを判別できるかは、
1枚まで出せるコイン・・・・・3種類まで 1~2枚まで出せるコイン・・・7種類まで 1~3枚まで出せるコイン・・・15種類まで 1~4枚まで出せるコイン・・・31種類まで 。。。
これらを全て満たせばよいことになる。
これを1回~6回の操作までで判断してやれば答えとなる。
事後
この問題・・・・好きかも(ポッ
ソースコード
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(); // 1枚だったらやらんでよし if (n == 0) return 1; // 1~5回の操作回数を試す 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; } } // 操作回数は最大でも6回 return 6; } };