TopCoder SRM 578 Div1
今日はTopCoderのSRMでしたね。
本日2回目のDiv1でしたが、Easyが解けて喜んでいたら、Challengeで軽く落とされるという・・・
では、私が間違えた点も含めてEasyのみ解説します。
Easy (250点)
この問題は、最大50×50サイズのフィールドの各マスにGoose（がちょう）とDack（アヒル）がある条件の下で存在することが分かっている時、Gooseの数として考えられる場合の数を求めなさい、という問題です。
与えられている条件は、
- ある場所にGooseがいるとき、マンハッタン距離がdist以下の場所にいる鳥はGooseである
- Gooseの数は正の偶数である
というものです。
着想としては、あるマスにいる鳥がGooseであるときに、マンハッタン距離の制約によりGooseであることが確定する鳥を1グループと考えるということです。
もしこのグループの中の鳥が1匹でもGooseであることが分かれば他の鳥もGooseですし、Dackである場合も同様です。
そこで、このグループが何個あり、それぞれのグループに何匹ずつ鳥がいるのかを最初に計算します。
計算が済んだら、どのグループを選んだ時に合計が偶数になるかを考えます。
Gooseの数の合計が偶数になるためには、奇数匹の鳥が含まれるグループを偶数個、偶数匹の鳥が含まれるグループを任意個選ぶ必要があります。
つまり、奇数匹の鳥が含まれるグループ数が$N_{even}$個あるならば、求めるべき場合の数は次のようになります。
$$ \left(sum_{i=0}^{N_{odd}/2} {}{N{odd}} \text{C}{2i} \right) \times \left(\sum{i=0}^{N_{even}} {}{N{even}} \text{C}_{i} \right) - 1 $$
最後に1を弾いているのは、どのグループも選ばれず、Gooseの数が0になる場合を除いているためです。
では、実際にコードを見てみます。
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cctype>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
ll MOD = 1000000007;
class GooseInZooDivOne {
public:
int W, H;
int bfs(vector<vector<int> >& group, vector<string>& field, int y, int x, int g, int dist) {
queue<pii> que;
que.push(pii(y, x));
int cnt = 0;
while(!que.empty()) {
pii p = que.front();
que.pop();
int xx = p.second;
int yy = p.first;
if(group[yy][xx] != 0) continue;
group[yy][xx] = g;
cnt++;
rep(i,H) {
rep(j,W) {
if(field[i][j] == 'v' && group[i][j] == 0) {
int man = abs(i-yy) + abs(j-xx);
if(man <= dist) {
que.push(pii(i, j));
}
}
}
}
}
return cnt;
}
void extgcd(ll a, ll b, ll& x, ll& y) {
if(b != 0LL) {
extgcd(b, a % b, y, x);
y -= a / b * x;
} else {
x = 1LL;
y = 0LL;
}
}
ll inv_mod(ll a, ll m) {
ll x, y;
extgcd(a, m, x, y);
return (x % m + m) % m;
}
ll combi(ll n, ll k) {
if(n < k)
return 0LL;
if(n - k < k)
k = n - k;
ll ans = 1;
for(ll i=1; i<=k; i++) {
ans = ans * (n-i+1) % MOD;
ans = ans * inv_mod(i, MOD) % MOD;
}
return ans;
}
int total(vector<int>& counts) {
int n_odd = 0;
int n_even = 0;
int n_v = counts.size();
rep(i,n_v) {
if(counts[i] % 2 == 0) n_even++;
else n_odd++;
}
ll s_odd = 0;
for(int i=0; i<=n_odd; i+=2) {
s_odd = (s_odd + combi(n_odd, i)) % MOD;
}
ll s_even = 0;
for(int i=0; i<=n_even; i++) {
s_even = (s_even + combi(n_even, i)) % MOD;
}
return (s_odd * s_even) % MOD - 1;
}
int grouping(vector<vector<int> >& group, vector<string>& field, int dist) {
int g = 1;
vector<int> counts;
rep(y,H) {
rep(x,W) {
if(field[y][x] == 'v' && group[y][x] == 0) {
int m = bfs(group, field, y, x, g, dist);
g++;
counts.push_back(m);
}
}
}
return total(counts);
}
int count(vector <string> field, int dist) {
H = field.size();
W = field[0].size();
vector<vector<int> > group(H, vector<int>(W, 0));
return grouping(group, field, dist);
}
}
やっている処理の流れとしては、
- 幅優先探索で各鳥がどのグループに入るのかを計算する
- グループの組み合わせの総数を前述の式により計算する
というものです。
ここで注意しなくてはならない（私がChallengeされた）ポイントは、総数を1,000,000,007で割った余りを求めなくてはならないということです。
グループの組み合わせの計算にはコンビネーション（${}_n \text{C}_k$）の計算が入りますが、ここの計算は注意が必要です。
単純には純粋な数の掛け算を割り算をすればよいのですが、余りの計算（modを用いる計算）では割り算をそのまま行うことができません。その代わりにmodを用いた場合の割り算というのをちゃんと行ってやらなくてはなりません。
もう少し数学的に言うと、これはmodにより与えられる同値関係に基づいた商集合上の割り算を考えていることになります。整数の集合は積の逆元が必ず存在するわけではないですが、modによる同値関係と整数の集合から作られる商集合は実は群をなしていて、積の逆元が存在します。
詳しい解説は蟻本（プログラミングコンテストチャレンジブック）の「modの世界」という項に書かれています（第1版ではP.242）。
さて、2回Div1を戦ってきたわけですが、前回はデバッグが間に合わず0問、今回は1時間手前でEasyを解くもChallengeで落とされるで、また1問も解けてません・・・。
そろそろ解かないとDiv2に落ちてしまうので、次もがんばっていきたいと思います。