TCO12 1B 250pt : FoxAndKgram

問題概要

長さN(<50)の整数列がある。この中からいくつか選んで長さkの棒をk本作りたい。長さkの棒を作るにはkをそのまま使うか、和がk-1になるものをつくるかのいずれかである。kの最大値を求める問題。

解法

答えについて全探索する。こういうのは上手い方法があるのかも知れないけど、間に合うなら愚直にやってよいと思う。もちろん愚直に書くのがバグ生みにくいときの話だけど。

acceptされたコード

#include <vector>
#include <cstring>
using namespace std;

const int MAX_L = 50;
const int MAX_N = 50;

bool used[MAX_N];

struct FoxAndKgram {

	int maxK(vector <int> len) {
		const int N = len.size();
		int ans = 0;
		for(int i=1; i<=2*MAX_L + 1; ++i){
			memset(used, false, sizeof(used));
			int count = 0;
			for(int k=0; k<N; ++k)if(!used[k]){
				if(len[k] == i){
					used[k] = true;
					count++;
					continue;
				}
				else{
					for(int l=k+1; l<N; ++l){
						if(!used[l] && len[k] + 1 + len[l] == i){
							used[k] = used[l] = true;
							count++;
							break;
						}
					}
				}
			}
			if(count >= i){
				ans = i;
			}
		}

		return ans;
	}

};