2012-02-24
SRM534 − 今日は出ましたがrating減
| 
（http://naoyat.hatenablog.jp/entry/2012/02/24/233000 からの転載）
- Easy(250): ◯<148.47>
- Medium(500): 撃沈<0>
- Hard(1000): 開いた<0>
12/20 in the room, 414/717 in Div1
1652 -> 1610
なんか最近EasyはDP有りで、Mediumはかなりうまく書かないとTLE/MLEになるぎりぎりの設定になってる印象。
Easy (250): EllysCheckers
- こういうNim系が相変わらず苦手で困る
- checkerの数が0の局面から逆方向に考えていくDP
- boardのサイズが最大20なので状態数は2^20=1048576
- 148.47 points (27'52'')
- Passed system test
#include <iostream>
#include <sstream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
#define sz(a) int((a).size())
#define pb push_back
#define rep(var,n) for(int var=0;var<(n);var++)
#define all(c) (c).begin(),(c).end()
class EllysCheckers {
public:
string getWinner(string board) {
int s=sz(board);
int n=1<<s;
vector<int> dp(n,-1);
dp[0] = 0;
for (int x=0; x<n; x++) {
for (int m=1; m<=x; m<<=1) {
if (m&x) {
int m_ = m << 1;
if (m_ < n && !(m_ & x)) {
int y = (x - m) | m_;
dp[y] = 1-dp[x];
}
int _mmm = m*7, mmmm = m*15;
if (mmmm < n && (x & mmmm) == _mmm) {
int y = (x - _mmm) | (_mmm << 1);
dp[y] = 1-dp[x];
}
}
}
if ((x & 1) == 0) {
int y = x|1;
dp[y] = 1-dp[x];
}
}
int b=0; rep(i,s-1) b = b*2 + ((board[i]=='o')?1:0);
return dp[b] ? "YES" : "NO";
}
};
Medium (500): EllysNumbers
- 数の集合が与えられ、互いに素であるような部分集合で積がnである組み合わせが何通りあるか
- nの約数以外は捨ててよさそう。1が入ってる場合は答えを2倍にすればよさそう。
- 集合の要素を端から1つずつ掛けたり掛けなかったりして行く感じのメモ化再帰を書いてみた。新たに掛ける数とそこまでの積とのgcdが1でない場合は掛けられない縛り
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
#define sz(a) int((a).size())
#define pb push_back
#define rep(var,n) for(int var=0;var<(n);var++)
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e) ((s).find(e)!=(s).end())
ll gcd(ll m, ll n)
{
if (m == 0 || n == 0) return 0LL;
if (m == 1 || n == 1) return 1LL;
if (m == n) return m;
while (1) {
if (m == 0) return n;
if (n == 0) return m;
if (m > n) m %= n; else n %= m;
}
}
class EllysNumbers {
vector<ll> ns;
int nn;
ll n_;
map<pair<ll,int>,ll> mm;
ll sub(ll x, int ix) {
if (ix == nn) return (x == n_ ? 1LL : 0LL);
pair<ll,int> k(x, ix);
if (found(mm,k)) return mm[k];
if (gcd(x, ns[ix]) == 1) {
return mm[k] = sub(x*ns[ix], ix+1) + sub(x, ix+1);
} else {
return mm[k] = sub(x, ix+1);
}
}
public:
long long getSubsets(long long n, vector <string> special) {
n_ = n;
stringstream ss;
tr(special,it) ss << *it; ss << " ";
string s = ss.str(); int sn = s.size();
ll a = 0;
vector<ll> nums;
rep(i,sn) {
if (s[i] == ' ') {
if (a >= 0) nums.pb(a);
a = -1;
} else {
ll b = (ll)(s[i] - '0');
if (a >= 0) a = a*10LL + b;
else a = b;
}
}
set<ll> nset; bool has1 = false;
tr(nums,it) {
if (*it == 1) { has1 = true; continue; }
if (n % *it) continue;
nset.insert(*it);
}
ns.assign(all(nset));
nn = ns.size();
if (nn == 0) return 0LL;
if (nn == 1 && ns[0] != n) return 0LL;
mm.clear();
return sub(1LL, 0) * (has1 ? 2 : 1);
}
};
- しかし撃墜される。TLE？MLE？
再考
- 積の要素が互いに素であるという条件はもっと活用すべき。nも集合各要素も素因数分解してみて、例えばnが2^3を持つなら2^2,2^1を持つ要素は排除できるよね
- n≦1e18ならnは高々15種類の素数（の累乗）の積と考えてよさそう。cf. (2^1)*(3^1)*(5^1)*(7^1)*(11^1)*(13^1)*(17^1)*(19^1)*(23^1)*(29^1)*(31^1)*(37^1)*(41^1)*(43^1)*(47^1)=614889782588491410
- nとspecial integersをそれぞれ nに含まれる素因数の有無をビットのon/offで表したら最長15ビット(<32768)
- special integersは高々500種類なので500*32768=16384000; long longだと131072000バイトでMLE。
- もしかして答えが32bit intを超えることがない？だとしたら32bit intで確保して65536000バイト。
- でもMLE…もしかしてこれって64MB制限に引っかかる？
- practice roomで実際にアロケートできたのがsizeof(int)*484*32768=63438848バイト。
- ああーもういいや最初の484個だけメモって残り16個ぐらい何度でも再帰させてしまえ
- これでpassed system test
#include <iostream>
#include <sstream>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
#define sz(a) int((a).size())
#define pb push_back
#define rep(var,n) for(int var=0;var<(n);var++)
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e) ((s).find(e)!=(s).end())
ll gcd(ll m, ll n)
{
if (m == 0 || n == 0) return 0LL;
if (m == 1 || n == 1) return 1LL;
if (m == n) return m;
while (1) {
if (m == 0) return n;
if (n == 0) return m;
if (m > n) m %= n; else n %= m;
}
}
class EllysNumbers {
vector<int> ns; // 15bit
int nn, allocated;
int n_; // 15bit
int *mm;
ll sub(int x, int ix) { // 15bit, 500=9bit
if (ix == nn) return (x == n_ ? 1LL : 0LL);
int k = (ix << 15) | x;
if (ix < allocated && mm[k] >= 0) return mm[k];
ll ans = sub(x, ix+1);
if ((x & ns[ix]) == 0) ans += sub(x | ns[ix], ix+1);
if (ix < allocated) mm[k] = ans;
return ans;
}
bool has1;
public:
bool prepare(long long n, vector<string> special) {
// special integersをパース
stringstream ss;
tr(special,it) ss << *it; ss << " ";
string s = ss.str(); int sn = s.size();
ll a = 0;
vector<ll> nums;
rep(i,sn) {
if (s[i] == ' ') {
if (a >= 0) nums.pb(a);
a = -1;
} else {
ll b = (ll)(s[i] - '0');
if (a >= 0) a = a*10LL + b;
else a = b;
}
}
// エラトステネスのふるい
char sieve[32768+1];
memset(sieve, 1, 32768+1);
sieve[0] = sieve[1] = false;
for (int i=3; i<32768; i+=2) {
sieve[i+1] = false;
if (!sieve[i]) continue;
for (int j=i*2; j<32768; j+=i) sieve[j] = false;
}
int primes[3512], j=0;
rep(i,32768) if (sieve[i]) primes[j++] = i; // 3512 primes in [0 .. 32767]
// special integers の中で要らない子を捨てつつ、それぞれを素因数分解
set<ll> nset; has1 = false;
set<int> used_primes; map<int,int> max_fact;
map<ll,map<int,int> > pset;
tr(nums,it) {
int num = *it; if (num == 1) { has1 = true; continue; }
if (n % num) continue;
// prime factorization
map<int,int> ps;
int x = num;
rep(j,3512){
int prime = primes[j];
while (x % prime == 0) {
if (found(ps,prime))
ps[prime]++;
else
ps[prime] = 1;
x /= prime;
}
}
if (x > 1) ps[x] = 1;
tr(ps,pt) {
used_primes.insert(pt->first);
if (found(max_fact, pt->first))
max_fact[pt->first] = max(max_fact[pt->first], pt->second);
else
max_fact[pt->first] = pt->second;
}
nset.insert(num);
pset[num] = ps;
}
nn = nset.size();
if (nn == 0) return false;
if (nn == 1 && *nset.begin() != n) return false;
// special integersで使った素数のみでnを素因数分解。できなければ return 0
ll x = n;
map<int,int> n_fact;
tr(max_fact,it) {
ll prime = (int)it->first;
int f = 0, maxf = it->second;
while (x % prime == 0) {
++f; x /= prime;
}
if (f) n_fact[prime] = f;
if (f > maxf) return false;
}
if (x != 1) return false;
map<int,int> n_fact_map;
n_ = 0;
int ix = 0;
tr(n_fact,it) {
n_ |= (1 << ix);
n_fact_map[it->first] = ix++;
}
// nで使われていない素因数を含むspecial integersを排除
ns.clear();
tr(pset,it) {
int bs = 0;
bool use_this = true;
tr(it->second,jt) {
int prime = jt->first, f = jt->second;
if (!found(n_fact, prime) || f != n_fact[prime]) { use_this = false; break; }
bs |= (1 << n_fact_map[prime]);
}
if (use_this) ns.push_back(bs);
}
nn = ns.size();
return true;
}
long long getSubsets(long long n, vector<string> special) {
if (!prepare(n, special)) return 0LL;
//mm.assign(500*32768, -1);
allocated = 0;
for (int sz=500; sz>0; --sz) {
mm = (int *)malloc(sizeof(int)*sz*32768);
if (mm) { allocated = sz; break; }
}
ll ans = 0;
if (mm) {
memset(mm, -1, sizeof(int)*allocated*32768);
ans = sub(0, 0) * (has1 ? 2 : 1);
free((void*)mm);
}
return ans;
}
};
Hard (1000): EllysString
- Mediumを提出して５分ぐらい残ってたので開いてみた。Levenshtein距離的な何かを求める問題。文字の置き換えと、隣接する2文字の交換が許されている。
- あとで考える
コメント
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20120224