Hatena::Grouptopcoder

isa@procon このページをアンテナに追加 RSSフィード

2011-09-11

SRM 517 Div.2

13:25

久々の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((alpha < tgt && beta < tgt) || (isPrime(alpha) && isPrime(beta))){

return false;

}

if(!isPrime(alpha) && !isPrime(beta)){

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";

}

}

2011-08-07

Codeforces #80 Div2

23:14

oo-x- +0/-1 1386pts,331st

A,B:やるだけ

C:グラフよくわからない。AOJでグラフの練習をするべき

D:

Systemで落ちた。nの偶奇で場合分け、偶は末尾から1つおきに置いて

先頭まで来たらまた後ろから置く。

nが奇数の場合がめんどくて

k=2なら末尾に詰める(Test Caseにあった)

それ以外なら偶と同じように置いていく

という方針でやっていったけどダメでした。

Hack/Challengeはほんと気をつけないとダメだな。TCから連続で2回

変数読み間違えて手実行ミスってる。

2011-08-06

KUPC

22:57

気づいたら始まっていたので50分ぐらい経過してから参加。

ooo------ 300pts/2:08 96th

A.やるだけ

B.DP書くだけ

C.

こういうタイプの問題は初めてみた。

同じ文字をsuffixとして返し続ければ勝てるという方針で組んだ。

初め何を勘違いしたか、AIから同じ文字で何度も返ってくると思ってしまって時間を食った。

実際には2文字なので、suffixとして選んだ文字だけ2回返ってくる可能性がある。

suffixをxとしてみると

?x

<-xa

?ax

<-xx

?xax

あとは2文字目として使ったかどうかを見ていけば良いだけ。

(実際のしりとりで1文字ってダメなルールでやってた記憶がある)

D.

方針思いつかず。DFSでやっていけばできそうな気はしたけど最悪どのくらい掛かるのか

見積もれず、書いてTLEになりそうなので一旦飛ばし。

E.

何かしらで区間内のFox Numberでないものを調べるんだとは思いつつも

方法解らず。

あとは出かけてしまったので手つかずでした。

Dがgreedyってのがよくわからない。

もう1問解きたかったです。