SRM 380 500pt: CompilingDecksWithJokers

TopCoder

問題概要

N(<50)種類のカードとジョーカーのあるカードがある。ジョーカーはJ(<5*10^8)枚あり、それ以外のカードはA[i](<5*10^8)枚ある。これから最大いくつのデッキを作ることができるか求める問題。デッキとは、異なるN種類のカード1組、または異なるN-1種類のカード+ジョーカーである。

考えたこと

  • サンプルが弱くて参考にならん。取りあえず非自明なケースを突っ込んでおく。
  • 単調性から二分探索臭がする。冷静に考えると別に二分探索で無くても解けそうな気はするが、判定問題に落とした方が問題が単純になるので二分探索で。
  • target組のデッキを作ろうとすると、target以下の毎数しかないカードはジョーカーで補填する必要がある。で、補填した分は他のカードの枚数を減らさなくてはならない。
  • カードを減らしすぎてもダメで、ジョーカーを使いすぎてもダメ、と言う風にすれば判定できる。
  • 投げた。無事Accept。

practiceで通ったコード

計算量O(log(J+MAX_A) * N^2)。

#include <vector>
using namespace std;

typedef long long int64;

struct CompilingDecksWithJokers {

	int maxCompleteDecks(vector <int> cards, int jokers) {
		int low = 0, high = 1<<30;
		while(high - low > 1){
			int mid = (high + low)/2;
			if(check(cards, jokers, mid)){
				low = mid;
			}
			else{
				high = mid;
			}
		}
		return low;
	}

	bool check(vector<int> cards, int64 joker, int target){

		//不足する分を埋めることができるか？
		const vector<int> original = cards;
		for(int i=0; i<(int)cards.size(); i++)if(target > original[i]){
			int diff = target - original[i];
			for(int j=0; j<(int)cards.size(); j++)if(i!=j){
				cards[j] -= diff;
				if(cards[j] < 0){
					return false;
				}
			}
			joker -= diff;
		}

		return joker >= 0;
	}

};

計算量を落とす

  • 判定部分の計算量をO(N)まで落とせる。
  • 補填するのに必要な枚数を覚えておいて、その枚数がJ以下かつtarget以下ならOK。
  • でも個人的にはO(N^2)のやつの方がわかりやすかった。
  • 必要性は明らかだけど、十分性がしばらく分からなかった。
	bool check(const vector<int>& cards, int joker, int target){

		int64 offset = 0;
		for(int i=0; i<(int)cards.size(); i++){
			offset += max(0, target - cards[i]);
		}

		return offset <= target && offset <= joker;
	}

おまけ

  • デッキの定義を、N-1枚の全て異なるカードの組、とすればジョーカーを特別扱いする必要はなくなる。A = {10, 15}, J = 3はこのデッキの定義だと A = {10, 15, 3}と同じ。
  • でもこういう出題のされ方をされると却って難しく見える。