SRM 669 DIV1 Easy - SubdividedSlimes

問題

https://community.topcoder.com/stat?c=problem_statement&pm=13946&rd=16549

解き方

すべての場合の数を考えるとはまってしまう。
逆に制約条件を考えると、Sが与えられた時、最大まで分割した時は１がS個並ぶ、
つまり最大でS-1回分割することができる。

次に、N回分割するとき、その数の最大は均等に分割すると得られる。
よって、分割数を２〜S-1まで試していき、最大がMを超えたものが答えになる。

コード

class SubdividedSlimes {

public: int needCut(int S, int M) {

for(int i=2;i<=S;i++){
vector<long long> num;
FORE(j,0,i)num.push_back(S/i);
FORE(j,0,S%i)num[j]++;

long long total=0;
FORE(j,0,i)total+=num[j];
long long sum=0;
FORE(j,0,i)sum+=num[j]*(total-num[j]);
if(sum/2>=M)return i-1;
}

return -1;
}

};

SRM 673 DIV1 Easy - BearCavalry

問題

https://community.topcoder.com/stat?c=problem_statement&pm=14081&rd=16616

解き方

w[0]について各組み合わせを決めることで、最大にならければならないスコアが決まる。
あとは残りについて、その数を超えないように全ての組み合わせ数を求める。

ここで各兵士について、乗ることができる馬の数を考える。
この数でソートすることで、i番目の兵士は、「乗ることのできる馬の数-(i-1)」が選ぶことのできる数であり、よって組み合わせていく順番が一意に決まる。

ある値（最大スコア）を固定することで、残りを貪欲法で選ぶことができないか、選ぶことのできる観点（各兵士について乗ることのできる馬の数）がないか考える。

コード

class BearCavalry {

public:

int countAssignments(vector<int> warriors, vector<int> horses) {
long long ret=0;
int n=warriors.size();
int MOD=1000000007;

FORE(i,0,n){
int value=warriors[0]*horses[i];
int cur[n-1];
memset(cur,0,sizeof(cur));
FORE(j,0,n-1)FORE(k,0,n)if(k!=i && warriors[j+1]*horses[k]<value)cur[j]++;
sort(cur,cur+n-1);
long long tmp=1;
FORE(j,0,n-1)tmp=(tmp*max(0,cur[j]-j))%MOD;
ret+=tmp;
}

return ret%MOD;
}

};

SRM 371 DIV1 Easy - SpiralRoute

問題

http://community.topcoder.com/stat?c=problem_statement&pm=8262&rd=10787

解き方

最大ケースの時は5000*5000なのでメモリが足りない。
そのため、なにかしら工夫する必要がある。

今回width,lengthともに3以上のときはwidth-2,lengh-2かつスタート位置(r,c)を(r+1,c+1)に
したものと等しくなる。

最後にwidth<=2もしくはlength<=2となるのでこれは簡単な場合分けで解ける。

コード

class SpiralRoute {

public: vector<int> thronePosition(int width, int length) {
int r=0,c=0;
while(width>=3 && length>=3){
width-=2,length-=2;
r++,c++;
}

if(length==1)r+=width-1;
else if(length==2)c++;
else if(width==1)c+=length-1;
else c++;

vector<int> ans(2);
ans[0]=r,ans[1]=c;

return ans;
}

};

SRM 663 DIV1 Easy - ABBADiv1

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13922&rd=16512

解き方

initialからtargetを生成するよう順に解いていき、部分列が存在しないようなら
打ち切ることで、候補数は限られるので時間内に解くことができる。
targetからinitialに戻せるか試しても良い。

コード

class ABBADiv1 {

public:

string rev(string str){
string ret="";
for(int i=str.size()-1;i>=0;i--)ret+=str[i];
return ret;
}

bool dfs(string cur,string target){
if(cur.size()>target.size())return false;
if(cur.size()==target.size()){
return cur==target;
}

bool valid=false;

string s1=cur+'A';
if(target.find(s1)!=string::npos || target.find(rev(s1))!=string::npos){
valid|=dfs(s1,target);
}
string s2=cur+'B';
if(target.find(s2)!=string::npos || target.find(rev(s2))!=string::npos){
valid|=dfs(rev(s2),target);
}

return valid;
}

string canObtain(string initial, string target) {
return dfs(initial,target) ? "Possible" : "Impossible";
}

};

SRM 399 DIV1 Easy - AvoidingProduct

問題

http://community.topcoder.com/stat?c=problem_statement&pm=8758&rd=12171

解き方

zの探索を枝刈りすることによって、ほぼx,yのすべての組み合わせだけ調べればよいので
O(10^6)で全探索可能。

調べる範囲として、NGの値の上限は1000のため取りうる値は1001まで
調べる必要がある。上限値の設定によるエラーケースに注意。

コード

class AvoidingProduct {

public: vector<int> getTriple(vector<int> a, int n) {
set<int> s;
FORE(i,0,a.size())s.insert(a[i]);

vector<int> ans(3,1001);
for(int x=1;x<=1001;x++)if(s.find(x)==s.end()){
for(int y=x;y<=1001;y++)if(s.find(y)==s.end()){
for(int z=y;z<=1001;z++)if(s.find(z)==s.end()){
int cur=abs(ans[0]*ans[1]*ans[2]-n);
if(cur>abs(x*y*z-n)){
ans[0]=x,ans[1]=y,ans[2]=z;
}
if(abs(x*y*z-n)> abs(x*y*(z-1)-n))break;
}
}
}

return ans;
}

};