Easy ("GooseInZooDivOne", 250)
ローカルで大丈夫っぽかったので投げてみたら、最大盤面(50x50)を'v'で埋め尽くしたケースでTLEが出た。ローカルでそのケースをやっても -O2 なら333msecで終了するのになんで?
もしかして:サーバ激遅
サーバで実行してみるにはArenaのTEST機能を使えばいい。
http://topcoder.g.hatena.ne.jp/agw/20130121/1358797527
vector<string> fieldは
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
を + ボタンで50回追加して(でいいのかな)
int dist = 0 でTEST実行
遅い…
ローカルでは余裕な提出コード
#include <iostream> #include <sstream> #include <cstdio> #include <cmath> #include <cctype> #include <algorithm> #include <string> #include <vector> #include <deque> #include <stack> #include <queue> #include <list> #include <map> #include <set> #define NDEBUG // BEGIN CUT HERE #include "cout.h" #undef NDEBUG // END CUT HERE #include <cassert> 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(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i) #define found(s,e) ((s).find(e)!=(s).end()) #define MOD 1000000007LL ll add(ll x, ll y) { return (x + y) % MOD; } ll sub(ll x, ll y) { return (x - y) % MOD; } ll mul(ll x, ll y) { return (x * y) % MOD; } ll pow(ll x, ll y) { ll v = 1; for(;y;x=mul(x,x),y>>=1) if(y&1) v = mul(v, x); return v; } ll div_(ll x, ll y) { return mul(x, pow(y, MOD-2)); } ll C(ll n, ll k) { // nCk pair<ll,ll> p(n, k); // if (found(cmm, p)) return cmm[p]; ll v = 1; for (ll i=1; i<=k; ++i) v = div_(mul(v, n-i+1), i); return v; } ll twopow(ll x) { // 2^x ll a = 1LL; rep(i,x) a = mul(a, 2); return a; } class UnionFind { vector<int> data; public: UnionFind(int size) : data(size, -1) { } bool unionSet(int x, int y) { x = root(x); y = root(y); if (x != y) { if (data[y] < data[x]) swap(x, y); data[x] += data[y]; data[y] = x; } return x != y; } bool findSet(int x, int y) { return root(x) == root(y); } int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } int size(int x) { return -data[root(x)]; } }; class GooseInZooDivOne { public: int count(vector<string> field, int dist) { int W=sz(field[0]), H=sz(field), S=W*H; // 50x50=2500 stringstream ss; rep(i,H) ss << field[i]; string f = ss.str(); UnionFind uf(S); for (int i=0; i<S-1; ++i) { int xi = i % W, yi = i / W; if (f[i] == '.') continue; for (int j=i+1; j<S; ++j) { if (f[j] == '.') continue; int xj = j % W, yj = j / W; int md = abs(xi-xj) + abs(yi-yj); if (md <= dist) uf.unionSet(i, j); } } map<int,int> cnt; rep(i,S){ if (f[i] == '.') continue; int r = uf.root(i); ++cnt[r]; } int even=0, odd=0; tr(it,cnt){ int /* r = it->first,*/ c = it->second; if (c & 1) ++odd; else ++even; } if (even == 0 && odd == 0) return 0; ll ans = 0LL; ll tp = twopow(even); // 2^even for (int i=0; i<=odd; i+=2) { ll ci = C(odd, i); ans = add(ans, mul(tp, ci)); } ans = (ans + MOD - 1) % MOD; return (int)ans; } };
じゃああれだ... 2^n とか nCk の計算を高速化するしかない
vector<vector<ll> > c_gen(int c_max) { vector<vector<ll> > c(c_max+1); c[0].assign(1, 1LL); // 0C0 for (int i=1; i<=c_max; ++i) { c[i].assign(i+1, 1LL); for (int j=1; j<i; ++j) { ll c_ij = (c[i-1][j-1] + c[i-1][j]) % MOD; c[i][j] = c_ij; } } return c; } ... ll twopow(ll x) { // 2^x ll b = 2LL, r = 1LL; while (x) { if (x & 1) { r = mul(r, b); } x >>= 1LL; b = mul(b, b); } return r; } ... class GooseInZooDivOne { public: int count(vector<string> field, int dist) { ... vector<vector<ll> > c = c_gen(odd); for (int i=0; i<=odd; i+=2) { ll ci = c[odd][i]; // ll ci = C(odd, i); ...
今度は 56.166msecなので大丈夫。
注意点
odd=0な場合もあるので 0C0=1がちゃんと出るようにしておくこと。(一回引っかかった)