2012 TCO Round 1B Easy - FoxAndKgram (○)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11809&rd=15091
・複数の長さの棒が与えられ、ここからK-gramを作りたい。
・K-gramとはK個からなる集合で、
各要素は長さKの棒もしくは2つの棒を組み合わせて長さK-1のものとなる。
・与えられた棒から作ることのできるK-gramのうち、最も大きいKのものを求める。
解き方
・棒の個数は最大５０個、長さも最大５０なので全探索ができそう。
・すべてのKに対してK-gramが作ることができるか判定すればよい。
・判定の方法としては、棒の長さでソートし１個の棒で成り立つものをカウント後、
それ以下の長さのペアを左側と右側双方から探索すればよい。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class FoxAndKgram {
public: int maxK(vector<int> len) {
int n=len.size();
sort(all(len));
int ret=0;
FORE(i,1,n+1){
int l=0,r=n-1,cnt=0;
while(r>=0 && len[r]>=i){
if(len[r]==i)cnt++;
r--;
}
while(l<r){
if(len[l]+len[r]>i-1)r--;
else if(len[l]+len[r]==i-1){
l++;
r--;
cnt++;
}
else l++;
}
if(i<=cnt)ret=max(ret,i);
}
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class FoxAndKgram {
public: int maxK(vector<int> len) {
int n=len.size();
sort(all(len));
int ret=0;
FORE(i,1,n+1){
int l=0,r=n-1,cnt=0;
while(r>=0 && len[r]>=i){
if(len[r]==i)cnt++;
r--;
}
while(l<r){
if(len[l]+len[r]>i-1)r--;
else if(len[l]+len[r]==i-1){
l++;
r--;
cnt++;
}
else l++;
}
if(i<=cnt)ret=max(ret,i);
}
return ret;
}
};
