SRM724 Lv2 : GravityPuzzle
作成日：2017.11.29
最終更新日：2017.11.29
問題概要
$r$行$c$列のマス目があり、いくつかのマスには箱がある。
初めはマス目に重力はかかっていないが、上下左右のいずれかの方向に重力を発生させる操作を任意の回数だけ行える。
箱は重力のかかった方向に空きマスがある限り移動する。
操作を適切に行うことで与えられたマス目の状態$board$にできる箱の初期配置の数を$10^9 + 7$で割った余りを求めよ。
制約
$1 \leq r,c \leq 50$
文字.は空きマス、文字#は箱を表す
考え方
$board$は条件を満たす初期配置の一つであるのは明らかだから、それ以外の配置で条件を満たすものを考える。
このような配置から$board$にするためには、操作を1回以上行う必要がある。
つまり、$board$に対して操作を行っても不変となるような操作がなければならない。
この判定は容易に行うことができる。
上下左右のいずれの操作に対しても不変でなかった時、答えは$board$の1通りである。
上下のうちのいずれかの操作に対して不変であり、左右の操作に対して不変でなかった時、初期配置から左右への操作を行うことはできない。
よって配置は列ごとに見れば良い。
すなわち、箱が$b$個ある列の初期配置としてあり得るのは${}_c C_b$通りである。
また、これは上下を左右と入れ替えても成り立つ。
最後に上下も左右もいずれかの操作に対して不変であった時を考える。
先に上下方向の操作を行うとする。
後から左右方向の操作を行うことから、各列の箱の個数をソートした時に$board$の各列の箱の個数をソートしたものと一致していれば良い$(*)$。
箱の個数を各列に割り当てた後は、前の段落で述べたものと同じである。
このことは左右方向の操作を先に行う時も同じであるが、重複が生じる。
重複するのは、どちらの方向の操作を先に行っても$board$になる初期配置である。
これは、各列及び各行に含まれる箱の個数がともに$(*)$を満たす時であり、この場合の数は行及び列それぞれの箱の個数の割り当て方の積である。
なぜなら、割り当てた時に配置は一意に定まるからである。
ソースコード
マクロ等はこちら
const int MC = 55;
const LL mod = 1e9+7;
const int MAX_COMB = 222;
LL fct[MAX_COMB+1];
LL invfct[MAX_COMB+1];
void build(){
fct[0] = fct[1] = 1;
repp(i,2,MAX_COMB+1){
fct[i] = fct[i-1] * i % mod;
}
LL x = fct[MAX_COMB];
invfct[MAX_COMB] = 1;
for(int i = mod - 2 ; i > 0 ; i >>= 1){
if(i % 2 == 1) (invfct[MAX_COMB] *= x) %= mod;
(x *= x) %= mod;
}
repm(i,MAX_COMB,0){
invfct[i-1] = invfct[i] * i % mod;
}
}
LL comb(int x , int y){
if(x < 0 || x < y) return 0;
return fct[x] * invfct[y] % mod * invfct[x-y] % mod;
}
class GravityPuzzle {
int cw[MC] , ch[MC] , c[MC];
public:
int count(vector<string> board) {
build();
int h = board.size();
int w = board[0].size();
int bh = 0, bw = 0;
repp(i,0,h){
int x = 0;
cw[i] = board[i][0]=='#'?1:0;
repp(j,1,w){
if(board[i][j] != board[i][j-1]) ++x;
if(board[i][j] == '#') ++cw[i];
}
if(x>1) bw = -1;
if(x==1){
if(board[i][0]=='#'){
if(bw == -1 || bw == 2) bw = -1;
else bw = 1;
} else {
if(bw == -1 || bw == 1) bw = -1;
else bw = 2;
}
}
}
repp(j,0,w){
int x = 0;
ch[j] = board[0][j]=='#'?1:0;
repp(i,1,h){
if(board[i][j] != board[i-1][j]) ++x;
if(board[i][j] == '#') ++ch[j];
}
if(x>1) bh = -1;
if(x==1){
if(board[0][j]=='#'){
if(bh == -1 || bh == 2) bh = -1;
else bh = 1;
} else {
if(bh == -1 || bh == 1) bh = -1;
else bh = 2;
}
}
}
if(bw < 0 && bh < 0) return 1;
LL ans = 1;
if(bw < 0){
repp(j,0,w){
ans = ans * comb(h,ch[j]) % mod;
}
return ans;
}
if(bh < 0){
repp(i,0,h){
ans = ans * comb(w,cw[i]) % mod;
}
return ans;
}
LL p = 1 , q = 1 , r = 1 , s = 1;
fill(c,c+MC,0);
repp(i,0,h){
c[cw[i]]++;
r = r * comb(w,cw[i]) % mod;
}
p *= fct[h];
repp(i,0,MC) p = p * invfct[c[i]] % mod;
fill(c,c+MC,0);
repp(i,0,w){
c[ch[i]]++;
s = s * comb(h,ch[i]) % mod;
}
q *= fct[w];
repp(i,0,MC) q = q * invfct[c[i]] % mod;
ans = (r * p + s * q + mod - p * q) % mod;
if(ans < 0) ans += mod;
return ans;
}
};解法まとめ
まず$board$が操作に対して不変かどうかを判定する。(36-72行)
どの方向に対しても不変でなければ答えは$1$である。(73行)
一方向のみ不変であればその方向に沿った1行(列)それぞれで考えれば良い。(75-86行)
どちらの方向も不変であれば、先に操作する方向を決めて各行(列)に箱の個数を割り当て、一方向のみ不変である時と同様に計算する。
但し、重複があるのでその分は引く必要がある。(87-105行)
SRM724の他の問題 Lv1 Lv3