TopCoder SRM #716 div2 (Easy,Middium)

所感

Easyの方を、最初律儀に全順列試そうとしていました。アホです。

何とか提出して(110点くらいだった)Middiumも方針立てたのですが、問題文中の

ab<=bc<=ca を見逃していました。ソートして場合分けしてたら時間切れ。悔しい。

 

Easy
https://community.topcoder.com/stat?c=problem_statement&pm=14628

与えられたxについて、xの各桁の数字を並び替えることで、元のxの倍数であるような数字を作ることが出来るかを判定する。

 

DFS(深さ優先探索)で順列作ろうと2,30分くら奮闘してました。アホです。

並び替えて作った数字はxの倍数なので、xの倍数からxのアナグラムを探せばいい。

因みにvector は全ての要素が等しいかどうかの比較演算が出来る...今回知りました。

#include <bits/stdc++.h>
typedef long long ll;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
using namespace std;

class Permutiple {

public
:
string isPossible(int x) {

vector<int> xnum;
int x_=x;
while(x_>0) {
xnum.push_back(x_%10);
x_/=10;
}
sort(ALL(xnum));

bool can = false;
REP(i,8) {
//2x<=multix<=9x
int multix=x*(i+2);
vector<int> mxnum;
while(multix>0){
mxnum.push_back(multix%10);
multix/=10;
}
sort(ALL(mxnum));
if(mxnum==xnum){
can=true;
break;
}
}

if (can) {
return "Possible";
} else {
return "Impossible";
}
}
};

 

Middum

https://community.topcoder.com/stat?c=problem_statement&pm=14624

文字列A,B,Cは、'1'か'0'のみで構成されている。二つの文字列の最長共通部分列の長さがそれぞれab, bc, caであるようなA,B,Cの例を示す。

 

面倒なのでどれか一つを"11111..."みたいにしたいなって思いました。例えばAを"111..."とすれば、Bを"11..(ab個)", Cを"11..(ac個)"とすればab,acについて達成できます。BCの最長共通部分列の長さはbcであるので、0で調節(B,Cに bc-ab個の0を加える)。コードではBが"11111..."となっています。

#include <bits/stdc++.h>
typedef long long ll;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
using namespace std;

class ConstructLCSEasy {
public:
string construct(int ab, int bc, int ca) {
string A,B,C;
A="";B="";C="";
REP(i,50){
B+="1";
}
REP(i,ab){
A+="1";
}
REP(i,bc){
C+="1";
}
REP(i,ca-ab){
A+="0";
C+="0";
}

return A+" "+B+" "+C;
}