SRM 517 Div.2

久々のSRM

まずクリックミスして500をopen.
初めての事態だったので焦って慌てて250を開いてしまったけど、500から初めるべきだったかもしれない。

250
題意が一度で取れず、2回読んだ。
まずh側に調べて何回Bに変えるかを調べる
board.size() == h ならreturn min(board.size(), board[0].size());
そうでないならw側も調べて足せばよい。
220ptsぐらい。

500
結構みるとDPで解いている人が多かったけど再帰で書きました。
与えられたxについて任意のy,z(x=yz)についてtgtが得られれば良い。

i)y,zのどちらかがtgtならその分割方法からはtgtは得られる
ii)そうでない場合、y,zのどちらもtgtより小さい、またはどちらも素数の場合はtgtは得られない
iii)y||zが合成数の場合、それについてtgtが得られるか再帰的に調べる

実際にはii)でどちらも素数の場合を忘れていてFailed System Test.
直後に足したらPassed System Test.

o-- +1/-0 272.05 210th(Div.2) 993->1047(+54)
まぁ4桁には戻した。

bool isPrime(int arg){
for(int i=2;i<=sqrt(arg);i++){
if(arg%i==0){
return false;
}
}
return true;
}

bool canGetFrom(int from, int tgt){
int alpha,beta;
bool res = true, tmpres = true;

if(from == tgt) return res;
for(int i=2;i<=sqrt(from);i++){
if(from%i == 0){
alpha = i;
beta = from/i;

//cout << "alpha = " << alpha << " beta = " << beta << endl;
if(alpha == tgt || beta == tgt){
continue;
}

if*1{
tmpres = canGetFrom(alpha,tgt) || canGetFrom(beta,tgt);
}else if(!isPrime(alpha)){
tmpres = canGetFrom(alpha,tgt);
}else if(!isPrime(beta)){
tmpres = canGetFrom(beta,tgt);
}
}
res &= tmpres;
}
return res;
}

string thePossible(int N, int tgt) {
bool res;

if(N%tgt != 0) return "No";

res = canGetFrom(N, tgt);

if(res){
return "Yes";
}else{
return "No";
}
}

*1:alpha < tgt && beta < tgt) || (isPrime(alpha) && isPrime(beta))){ return false; } if(!isPrime(alpha) && !isPrime(beta