問題
http://community.topcoder.com/stat?c=problem_statement&pm=13743&rd=16434
解き方
２つ行があるが、追加する木については上下のどちらに追加しても変わらないので
片方だけを考える。
すでに存在する木によって追加できるスペースはいくつかに区切られるが、
各区切りごとのセルの連続数によって、追加できる木の数が決まる。
コード
class DevuAndPlantingTrees {
public: int maximumTreesDevuCanGrow(vector<string> garden) {
int n=garden[0].size();
int used[n];
int ret=0;
memset(used,0,sizeof(used));
FORE(i,0,2)FORE(j,0,n)if(garden[i][j]=='*'){
if(j-1>=0)used[j-1]=1;
if(j+1<n)used[j+1]=1;
used[j]=1;
ret++;
}
int at=0;
while(1){
while(at<n && used[at])at++;
if(at>=n)break;
int l=at;
at++;
while(at<n && !used[at+1])at++;
ret+=(at-l+2)/2;
at++;
}
return ret;
}
};
public: int maximumTreesDevuCanGrow(vector<string> garden) {
int n=garden[0].size();
int used[n];
int ret=0;
memset(used,0,sizeof(used));
FORE(i,0,2)FORE(j,0,n)if(garden[i][j]=='*'){
if(j-1>=0)used[j-1]=1;
if(j+1<n)used[j+1]=1;
used[j]=1;
ret++;
}
int at=0;
while(1){
while(at<n && used[at])at++;
if(at>=n)break;
int l=at;
at++;
while(at<n && !used[at+1])at++;
ret+=(at-l+2)/2;
at++;
}
return ret;
}
};
Share this
Related Posts
SRM 618 DIV1 Easy - Family
問題
http://community.topcoder.com/stat?c=problem_statement&pm=10541&rd=15851
・有効グラフが２つ与えられる。
・それぞれのグラフは親と子の- SRM 410 DIV1 Easy - AddElectricalWires
問題
http://community.topcoder.com/stat?c=problem_statement&pm=8817&rd=12182
ノードが複数存在し、任意のノード同士がつながっている。
また、
- SRM 640 DIV1 Easy - ChristmasTreeDecoration (○)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=13551&rd=16083
・クリスマスツリーをデコレーションするのに、N個の星とN-1個
- SRM 549 DIV1 Easy - PointyWizardHats
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11965&rd=15171
解き方
上に載せるハットと下に載せるハットの組み合わ