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; } };