問題
http://community.topcoder.com/stat?c=problem_statement&pm=12746&rd=15703
グラフの各深さに対する頂点数が与えられる。
このとき、そのグラフの直径を求める。
解き方
グラフを最大のケースで作ってもよいが、場合分けをすれば簡単に求められる。
まず、答えの最小は各深さの頂点が１のとき、つまり深さ＋１（要素数）となる。
次に、直径の長さはその深さにおける頂点数が１もしくは２以上の場合しか影響されない。
②頂点数が２以上の場合
折り返し分の直径が増えるので、その値と比較して最大値を更新
①頂点数が１の場合
折り返し分はリセットされる。
リセットされた際の最大値の更新は①で比較済み。
コード
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 TheTree {
public: int maximumDiameter(vector<int> cnt) {
int n=cnt.size();
int ret=n;
int last=-1,len=0;
FORE(i,0,n){
if(cnt[i]==1){
last=i,len=0;
}
else{
len++;
ret=max(ret,n-last-1+len);
}
}
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 TheTree {
public: int maximumDiameter(vector<int> cnt) {
int n=cnt.size();
int ret=n;
int last=-1,len=0;
FORE(i,0,n){
if(cnt[i]==1){
last=i,len=0;
}
else{
len++;
ret=max(ret,n-last-1+len);
}
}
return ret;
}
};
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 TheTree {
public: int maximumDiameter(vector<int> cnt) {
int n=cnt.size();
int ret=0;
vector<int> vx;
vx.push_back(1);
FORE(i,0,n)vx.push_back(cnt[i]);
FORE(i,0,n+1)if(vx[i]==1){
int left=0,right=0,flag=0;
FORE(j,i+1,n+1){
if(vx[j]==1||flag)flag=1,left++;
else left++,right++;
ret=max(ret,left+right);
}
}
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 TheTree {
public: int maximumDiameter(vector<int> cnt) {
int n=cnt.size();
int ret=0;
vector<int> vx;
vx.push_back(1);
FORE(i,0,n)vx.push_back(cnt[i]);
FORE(i,0,n+1)if(vx[i]==1){
int left=0,right=0,flag=0;
FORE(j,i+1,n+1){
if(vx[j]==1||flag)flag=1,left++;
else left++,right++;
ret=max(ret,left+right);
}
}
return ret;
}
};