2008-12-25
SRM399 Div1 Easy: AvoidingProduct
走査範囲が狭くてシステムテスト落ち。書き直しの刑。（書き直しなのに6分17秒もかかったorz）
class AvoidingProduct {
public:
vector<int> getTriple(vector<int> a, int n) {
int dmin = 1000;
int uplim = 2000+a[0]+1; //2000あれば大丈夫っぽい
set<int> s; tr(a,it) s.insert(*it); // NGリスト
int amin=1001;
for(int i=1;i<=1000;i++) {
if (s.find(i)==s.end()) {amin=i;break;}
}
int am3=amin*amin*amin;
if (am3>n) { vector<int> ans(3,amin); return ans; }
vector<int> ans(3,-1);
for(int x=1;x<=uplim;x++){
if (s.find(x)!=s.end()) continue;
for(int y=x;y<=uplim;y++){
if (s.find(y)!=s.end()) continue;
int xy = x*y;
if(xy>uplim) break;
for(int z=y;z<=uplim;z++){
if (s.find(z)!=s.end()) continue;
int xyz = xy * z;
if(xyz>uplim) break;
int d = abs(n-xyz);
if (d<dmin) {
dmin = d;
ans[0]=x; ans[1]=y; ans[2]=z;
}
}
}
}
return ans;
}
};
SRM400 Div1 Easy: StrongPrimePower
ある数が素数の累乗(２乗以上）かを調べる。pow()とか出てこなくて12分ぐらいかかった。（けれど一発で通った）
素数判定にはMiller-Rabinを使っている。
template <typename T> T expt(T x, int n) // x^n
{
T y=1; for(int i=0;i<n;i++) y*=x; return y;
}
////
long long random(long long n)
{
return (long long)rand() % n;
}
long long check_nontrivial_sqrt_1(long long m, long long a)
{
long long r = (a * a) % m;
return (1LL < a && a < m-1 && r == 1)? 0LL : r;
}
long long expmod(long long base, long long exp, long long m)
{
if (exp == 0)
return 1LL;
else if (!(exp & 1))
return check_nontrivial_sqrt_1(m,expmod(base,exp/2,m));
else
return (base*expmod(base,exp-1,m)) % m;
}
bool miller_rabin_test(long long n)
{
return expmod((1LL+random(n-1)),n-1,n) == 1LL;
}
bool fast_prime(long long n, int times)
{
if (n == 1) return false;
if (n == 2) return true;
else if (!(n & 1)) return false;
for (int i=times; i>0; i--)
if (!miller_rabin_test(n)) return false;
return true;
}
////
class StrongPrimePower {
public:
vector<int> baseAndExponent(string n) {
long long n_ = 0; // 2-10^18=1000^6<2^60
for(int i=0;i<n.length();i++) {n_*=10; n_+=n[i]-'0';}
for (int q=59;q>=2;q--) {
double q_ = 1.0 / q;
double d_ = pow(n_,q_); long long p = (long long)(d_ + 0.0001);
if (p == 0) continue;
if (!fast_prime(p,3)) continue;
if (expt(p,q)==n_) {
vector<int> ans(2);
ans[0]=p; ans[1]=q; return ans;
}
}
vector<int> ans; return ans;
}
};
SRM401 Div1 Easy: FIELDDiagrams
DP。単純な問題だが手間取っている。DPでいきなりコーディングは空中分解しがち。
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n) for(int var=0;var<(n);var++)
class FIELDDiagrams {
public:
int fo;
vector<long long> memo;
long long sub(int last,int fieldOrder){
int ceil = min(last,fieldOrder);
if (ceil == 0) { return 1;}
int key=(ceil<<5)|fieldOrder;
if (memo[key]>=0) return memo[key];
long long count=1LL;
for(int ai=ceil;ai>0;ai--){
count += sub(ai,fieldOrder-1);
}
return memo[key] = count;
}
long long countDiagrams(int fieldOrder) {
fo = fieldOrder;
memo.resize(1024); fill(all(memo),-1);
long long count = 0LL;
for (int a1=fieldOrder;a1>0;a1--) {
count += sub(a1, fieldOrder-1);
}
return count;
}
};
SRM402 Div1 Easy: RandomSort
DP的問題。メモ化しないとTLE。状態の数はn^nあるが、vector<double>だとメモリ64MB制限に引っかかる。map<int,double>で必要なものだけメモ化するのが吉。
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n) for(int var=0;var<(n);var++)
template <typename T> T expt(T x, int n) // x^n
{
T y=1; for(int i=0;i<n;i++) y*=x; return y;
}
class RandomSort {
int n;
vector<int> perm;
//vector<double> memo;
map<int,double> memo;
int sig() {
int s=0;
tr(perm,it) s=s*n+(*it-1);
return s;
}
double sw(){
int key=sig();
// if(memo[key]>=0) return memo[key];
if(memo.find(key)!=memo.end()) return memo[key];
set<pair<int,int> > s;
rep(i,n){
int p = perm[i];
for(int j=i+1;j<n;j++){
int q = perm[j];
if (p>q) s.insert(make_pair(i,j));
}
}
if (s.size() == 0) return memo[key] = 0;
double cnt=0;
tr(s,it){
int i=it->first, j=it->second;
int p=perm[i], q=perm[j];
perm[i]=q; perm[j]=p;
cnt += 1 + sw();
perm[i]=p; perm[j]=q;
}
cnt /= s.size();
return memo[key] = cnt;
}
public:
double getExpected(vector<int> permutation) {
n=sz(permutation);
perm = permutation;
return sw();
}
};
SRM403 Div1 Easy: TheLuckyNumbers
10^9のループではTLEになるであろう数え上げ系。すこし手間取った(141.71points)。
こういうので200点以上とれるようになりたい。
int c(int n, int r)
{
if (n == 0 || r == 0 || r == n) return 1;
if (r > n-r) r = n-r;
return n * c(n-1,r-1) / r;
}
int expt(int x,int n){
int v=1; rep(i,n) v*=x; return v;
}
class TheLuckyNumbers {
public:
int s_(int k,int n){
int cnt=0;
rep(i,1<<k){
int u=0,m=1<<(k-1);
rep(j,k){u*=10; u+=(i&m)?7:4; m>>=1;}
if (n>=u) cnt++; else break;
}
return cnt;
}
int s(int k){
return expt(2,k);
}
int lns(int n){
if (n<4) return 0;
if (n<7) return 1;
if (n<44) return 2;
if (n>777777777) n=777777777;
int k=0,t=0,o=1;
int n_=n;
while(n_>0){ t=n_; n_/=10; o*=10; k++; }
o = (o-1)/9;
int o4=o*4, o7=o*7;
int kt=k;
int cnt=0;
if (n<o7) {
kt--;
if (n>=o4) {
cnt += s_(k,n);
}
}
rep(i,kt) cnt+=s(i+1);
return cnt;
}
int count(int a, int b) {
return lns(b)-lns(a-1);
}
};
SRM404 Div1 Easy: RevealTriangle
覆面算的な問題、と思ったけどそう難しくない。逆三角形の下から解いて行ける。
class RevealTriangle {
public:
vector<string> calcTriangle(vector<string> questionMarkTriangle) {
int rows=questionMarkTriangle.size(); //1-50
vector<vector<int> > v(rows);
rep(row,rows){
v[row].resize(rows-row);
rep(i,rows-row){
int c = questionMarkTriangle[row][i]-'0';
v[row][i] = (c < 0||9<c)?-1:c;
}
}
for(int row=rows-1;row>=0;row--){
int l=rows-row;
string qmt= questionMarkTriangle[row];
rep(z,l){
rep(i,l) {
if (v[row][i]<0) {
if (i>0 && v[row][i-1]>=0) {
v[row][i] = (10 + v[row+1][i-1] - v[row][i-1])%10;
} else if (i+1<l && v[row][i+1]>=0) {
v[row][i] = (10 + v[row+1][i] - v[row][i+1])%10;
}
}
}
}
}
vector<string> result(rows,"");
rep(row,rows){
stringstream ss;
rep(i,rows-row) ss << (char)(48+v[row][i]);
result[row] = ss.str();
}
return result;
}
};
SRM405 Div1 Easy: RelativePath
class RelativePath {
public:
string makeRelative(string path, string currentDir) {
vector<string> vp = split(path,'/'), vcd = split(currentDir,'/');
int lp=sz(vp), lcd=sz(vcd);
int common=0;
if(currentDir=="/") { lcd=1; common=0;}
else
for(int i=1;i<min(lp,lcd);i++){
if(vp[i]!=vcd[i]) break;
common++;
}
string dest=""; rep(i,lcd-1-common) dest+="../";
for(int i=1+common;i<lp;i++) {dest+=vp[i];if(i<lp-1)dest+="/";}
return dest;
}
};
SRM406 Div1 Easy: SymmetricPie
next_permutationを使ってBrute Force
class SymmetricPie {
public:
int getLines(vector<int> dogs) {
int N=sz(dogs);
sort(all(dogs));
int maxcnt=0;
while(1) {
int cnt=0;
vector<int> ac(N+1,0); ac[0]=0;
for(int i=0;i<N;i++) ac[i+1]=ac[i]+dogs[i];
for(int i=0;i<N;i++) {
if (ac[i]<50){
for(int j=i+1;j<=N;j++) {
if (ac[j]-ac[i]==50) cnt++;
}
}
}
if (maxcnt<cnt) maxcnt=cnt;
if (!next_permutation(all(dogs))) break;
}
return maxcnt;
}
};
SRM407 Div1 Easy: CorporationSalary
再帰的に計算。メモ化。
class CorporationSalary {
int N;
vector<long long> salary;
vector<vector<bool> > t;
long long decide_salary(int id){
if (salary[id] > 0) return salary[id];
long long s=0LL;
rep(j,N){
if(t[id][j]) s+=decide_salary(j);
}
if (s==0LL) s=1LL;
return salary[id] = s;
}
public:
long long totalSalary(vector<string> relations) {
N = relations.size(); //1-50
t.resize(N); tr(t,it) it->resize(N);
rep(i,N) rep(j,N) t[i][j]=(relations[i][j]=='Y');
salary.resize(N); tr(salary,it) *it=0;
long long total=0LL;
rep(i,N) total+=decide_salary(i);
return total;
}
};
SRM408 Div1 Easy: OlympicCandles
超簡単・・・なはずがSTLの操作でつまづく。
vector<int>から値が0の要素を削除するだけの簡単な仕事で。
tr(candles,it) if(!*it) candles.erase(it); →Segmentation Fault remove(all(candles),0); →消えてないっぽい。なんで？
ゴミを消さないと駄目らしい。従って
class OlympicCandles {
public:
int numberOfNights(vector<int> candles) {
for(int nights=1;;nights++){
sort(all(candles),greater<int>());
if(candles.size() < nights) return nights-1;
for(int i=0;i<nights;i++) candles[i]--;
candles.erase(remove(all(candles),0),candles.end());
}
}
};
コメント
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20081225