SRM 366 500pt: GuitarConcert

TopCoder

問題概要

ギターがN(<=10)本ある。各ギターについて、どの曲が演奏されるかのリストが与えられる(曲の数=M(<50))。次の順で優先順位を決めたときに選ばれる部分集合を求める問題。

  1. 演奏できる曲の多さ
  2. ギターの少なさ
  3. ギターの名前の辞書順で若い方

考えたこと

  • N=10って…。一瞬マッチング系の問題化と思ったがこれはどう見ても全探索。
  • 素朴な実装で計算量がO(2^N * N*(M+log N))位に見える。
  • 500にしては簡単な気もするので、疑心暗鬼になりながらコーディング。
  • 辞書順比較のあたりでちょっとつまづいたけど無事サンプルが通った。
  • 提出しても何事も無く通った。

practiceで通ったコード

#include <vector>
#include <string>
#include <set>
#include <algorithm>

typedef long long int64;

using namespace std;

struct GuitarConcert {

	vector <string> buyGuitars(vector <string> guitarNames, vector <string> guitarSongs) {

		vector<string> ret;
		const int N = guitarNames.size();
		const int M = guitarSongs[0].length();
		int best_count = 0;
		int least_count = 0;

		//全探索
		for(int bit=0; bit<(1<<N); bit++){
			int64 play = 0;
			for(int i=0; i<N; i++)if((bit>>i)&1){
				for(int j=0; j<M; j++)if(guitarSongs[i][j] == 'Y'){
					play |= (1LL<<j);
				}
			}

			//以下は更新処理
			int play_count = __builtin_popcountll(play);
			int guitar_count = __builtin_popcount(bit);
			vector<string> tmp;
			for(int i=0; i<N; i++)if((bit>>i)&1){
				tmp.push_back(guitarNames[i]);
			}
			sort(tmp.begin(), tmp.end());

			if(play_count >= best_count){
				if(play_count > best_count){
					best_count = play_count;
					least_count = guitar_count;
					ret = tmp;
				}
				else if( least_count > guitar_count ){
					least_count = guitar_count;
					ret = tmp;
				}
				else if( least_count == guitar_count && tmp < ret ){
					ret = tmp;
				}
			}
		}

		return ret;
	}

};