250 열어보니 이전에 돌았던 셋 같은 느낌이 강하게 들었지만 그냥 돌았음. binary search 250 과 DP 500, 그리고 DP 1000 으로 구성된 셋. 500 은 느리긴 느렸는데 풀긴 풀었고, 1000 은 한참 헤매다가 설마 이게 될까? 하고 1시간 17분째에 냈다. 결론은 PPP ㅠ 만세
250 IncredibleMachine
lang:cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cassert>
#include<numeric>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<deque>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define CLEAR(x,with) memset(x,with,sizeof(x))
#define sz size()
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;
const double eps = 1e-8;
struct IncredibleMachine
{
vector<double> solve2(double a, double b, double c)
{
double d = b*b - 4*a*c;
if(d < -eps) return vector<double>();
if(d < eps) return vector<double>(1, -b / (2*a));
vector<double> ret;
ret.push_back((-b + sqrt(d)) / (2*a));
ret.push_back((-b - sqrt(d)) / (2*a));
return ret;
}
double gravitationalAcceleration( vector <int> x, vector <int> y, int T )
{
double lo = 0, hi = 1e10;
REP(it,100)
{
double mid = (lo + hi) / 2;
double takes = 0, speed = 0;
REP(i,x.sz-1)
{
double c = hypot(x[i+1] - x[i], y[i+1] - y[i]);
double dy = y[i] - y[i+1];
double a = mid * dy / c;
vector<double> dt = solve2(0.5 * a, speed, -c);
assert(dt.sz && dt[0] > 0);
takes += dt[0];
speed += dt[0] * a;
}
if(takes < T)
hi = mid;
else
lo = mid;
}
return hi;
}
};
500 MazeWandering
내가 괜히 어렵게 푼 듯.. ㅠ 사실 그 외에도 Gaussian elimination 으로도 풀리더라.
lang:cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cassert>
#include<numeric>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<deque>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define CLEAR(x,with) memset(x,with,sizeof(x))
#define sz size()
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;
pair<double,int> cache1[51][51];
double cache2[51][51];
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
struct MazeWandering
{
vector<string> m;
int h, w;
double goUp(int y, int x, int py, int px)
{
double& ret = cache2[y][x];
if(ret >= 0) return ret;
ret = 0;
int child = 0;
REP(k,4)
{
int ny = y + dy[k], nx = x + dx[k];
if(ny == py && nx == px) continue;
if(ny < 0 || nx < 0 || ny >= h || nx >= w || m[ny][nx] == 'X') continue;
++child;
}
if(child == 0) return ret = 1; // we can only go up
REP(k,4)
{
int ny = y + dy[k], nx = x + dx[k];
if(ny == py && nx == px) continue;
if(ny < 0 || nx < 0 || ny >= h || nx >= w || m[ny][nx] == 'X') continue;
ret += 1.0 / (child + 1) * (goUp(ny, nx, y, x) + 1.0);
}
ret += 1.0 / (child + 1); // go straight up
ret *= (child + 1);
return ret;
}
pair<double,int> go(int y, int x, int py, int px)
{
if(y < 0 || x < 0 || y >= h || x >= w || m[y][x] == 'X') return make_pair(0, 0);
pair<double,int>& ret = cache1[y][x];
if(ret.first >= 0) return ret;
ret.first = goUp(y, x, py, px);
ret.second = 1;
REP(k,4)
{
int ny = y + dy[k], nx = x + dx[k];
if(ny == py && nx == px) continue;
pair<double,int> exp = go(ny, nx, y, x);
ret.first += exp.first + exp.second * goUp(y, x, py, px);
ret.second += exp.second;
}
return ret;
}
double expectedTime( vector <string> maze )
{
m = maze;
h = m.sz; w = m[0].sz;
REP(i,h) REP(j,w)
{
cache1[i][j].first = -1;
cache2[i][j] = -1;
}
REP(i,h) REP(j,w) if(m[i][j] == '*')
{
double expSum = 0;
int children = 0;
REP(k,4)
{
pair<double,int> expected = go(i + dy[k], j + dx[k], i, j);
expSum += expected.first;
children += expected.second;
}
return expSum / (children+1);
}
return -1; // oops
}
};
1000 SquareFreeSets
처음에는 sqrt(500) 까지만 서로 곱할 수 있겠지? 후후 하면서 22 밑까지만 다 돌리고 그 후로 DP 하려다 보니 당연 2x3x71 같은건 서로 곱할 수 있다. -_-;; n/primes[i] 이상이 되는 숫자들은 다 버려도 되겠지? 이거 개수만 유지할까 후후 했더니 안되길래 개수도 몇개 안되겠다 닥치고 벡터에 때려넣기 고고?
해서 간신히 맞음
lang:cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cassert>
#include<numeric>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<deque>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define CLEAR(x,with) memset(x,with,sizeof(x))
#define sz size()
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;
const ll M = 1000000007;
map<VI,ll> cache[501][501];
struct SquareFreeSets
{
VI primes;
int n, k;
ll go(int here, int numbers, VI subset)
{
if(here == primes.sz) return numbers ? 1 : 0;
while(!subset.empty() && subset.back() > n/primes[here]) subset.pop_back();
map<VI,ll>::iterator it = cache[here][numbers].find(subset);
if(it != cache[here][numbers].end()) return it->second;
ll& ret = cache[here][numbers][subset];
ret = go(here+1, numbers, subset) % M;
if(numbers < k)
{
VI next = subset;
next.pb(primes[here]);
sort(all(next));
(ret += go(here+1, numbers+1, next)) %= M;
}
REP(i,subset.sz)
{
VI next = subset;
next[i] *= primes[here];
assert(next[i] <= n);
sort(all(next));
(ret += go(here+1, numbers, next)) %= M;
}
printf("here %d, numbers %d, subset", here, numbers);
REP(i,subset.sz) printf(" %d", subset[i]);
printf(" => %Ld\n", ret);
return ret;
}
int countPerfect( int N, int K )
{
n = N; k = K;
primes.clear();
REP(i,501) REP(j,501) cache[i][j].clear();
primes.pb(2);
for(int i = 3; i <= N; i += 2)
{
bool ok = true;
REP(j,primes.sz) if(i % primes[j] == 0) { ok = false; break; }
if(ok) primes.pb(i);
}
VI nums;
return go(0, 0, nums);
}
};
