スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ZOJ Monthly, August 2012

久しぶりに参加する ZOJ Montly。
今回は komiya さん、lyoz さんとチームを組ませてもらった。
自分の担当分だけ書く。

Tags : プログラミング ZOJ

結果

A, C, E, H, J, K の 6/11 完
41 位

F, I はほぼ書きあがっていたのに通せなくて悔しい。

問題

F : Fruit Ninja
n 種類の果物があり、いくつかの果物 i に対しては
・ x[i] 個より少なく選ばないといけない
・ x[i] 個より多く選ばないといけない
という制約がある。一種類の果物に対して制約は高々一つ。
合計 m 個選ぶような組み合わせが何通りあるか、mod 10^8+7 で求めよ。

1 ≦ n ≦ 16
1 ≦ m ≦ 10^7

J : Just Another Information Sharing Problem
n 人の人がいる。
人 i は A[i] 個の情報をもっていて、そのうち B[i] 個以上 C[i] 個以下の情報を他の人に伝える。
人 m は最大でいくつの情報を得られるか。

1 ≦ n < 200
0 ≦ B[i] ≦ C[i] ≦ A[i] ≦ 10
異なる情報は高々 200 種類

K : Keep Deleting
文字列 A、B が与えられる。
B を左から見ていって、A が部分文字列として含まれる箇所が見つかったら、その部分を丸々 B から取り除き、
また左端から見ていく。
最終的に A が取り除かれなくなったら終わり。
A は何回取り除かれるか。

1 ≦ |A| ≦ 256
1 ≦ |B| ≦ 512000

解答

F
x[i] 個より多く選ぶという条件があれば、それをなかったことにして m-x[i]-1 個選ぶ問題と同じだから、少なく選ぶという条件だけ考えればいい。
どの果物にも制約がないときの場合の数は二項係数になるので、包除原理でうまくやれば答えが求まる。

実装量を減らそうと変な書き方をしていて、それで気づきにくいバグを埋め込んでしまっていた。

J
全員が人 m に向けて情報を発信すればよくて、しかも B[i] はいらない気がする。
いらない設定が情報が多すぎる。

左に人を、右に情報を頂点として置いて、最大流を流せばよい。

K
KMP の failure link をうまく使う。
B[i] で A とのマッチがはじめて完了したとすると、今 B[i-|A|] までのマッチした情報を引き続いて使いたいので、j=fail[i-|A|] として KMP の検索アルゴリズムを続ければよい。
二回目以降にマッチしたときが問題になって、どこまで戻ればいいかが自明じゃない。
A = "abcd", B = "aabcdbabcdcabcdd" などを考えればわかるように、穴ぼこがいっぱいできる。
これを解決するために連結リストを使う。穴ぼこができたら、それを消すようにリストを修正する。
リストの修正にかかる時間は、検索アルゴリズム全体で O(|B|) なのでよい。
BIT で二分探索しても同じことができる気がするけど、log^2 がついてやばい。

ソースコード

F
#include<cstdio>
#include<vector>
#include<cassert>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef long long ll;

const ll M=100000007;

int fact[10000101];

ll xgcd(ll a,ll b,ll &x,ll &y){
if(b==0){ x=1; y=0; return a; }
ll g=xgcd(b,a%b,y,x); y-=a/b*x;
return g;
}

ll modinv(ll a,ll m){
ll x,y;
if(xgcd(a,m,x,y)==1) return (x+m)%m;
return -1;
}

ll nCr(int n,int r){
if(n<r) return 0;
return (ll)fact[n]*modinv(fact[n-r],M)%M*modinv(fact[r],M)%M;
}

int main(){
fact[0]=1;
rep(i,10000100) fact[i+1]=(i+1LL)*fact[i]%M;

for(int n,m;scanf("%d%d",&n,&m),n;){
while(getchar()!='\n');

int a[16],minus=0;
rep(i,n) a[i]=m+1;
rep(i,n){
char s[128],t[128]; gets(s);
if(!s[0]) break;
sscanf(s,"%*s%s%*s%d",t,a+i);
if(t[0]=='g'){
minus+=a[i]+1;
a[i]=m+1;
}
}
m-=minus;

ll ans=0;
rep(S,1<<n){
int pc=0;
ll sum=0;
rep(i,n) if(S&1<<i) {
pc++;
sum+=a[i];
}
if(pc%2==0) ans+=nCr(m-sum+n-1,n-1);
else ans-=nCr(m-sum+n-1,n-1);
ans%=M;
}
if(ans<0) ans+=M;
printf("%lld\n",ans);
}

return 0;
}


J
#include<cstdio>
#include<vector>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int main(){
for(int n;~scanf("%d",&n);){
vector<int> man[200];
int lb[200],ub[200];
vector<int> X;
rep(i,n){
int m; scanf("%d%d%d",&m,lb+i,ub+i);
man[i].resize(m);
rep(j,m){
scanf("%d",&man[i][j]);
X.push_back(man[i][j]);
}
}
int tar; scanf("%d",&tar); tar--;

if(n==1){ printf("%d\n",man[tar].size()); continue; }

sort(X.begin(),X.end());
X.erase(unique(X.begin(),X.end()),X.end());

rep(i,n) rep(j,man[i].size()) man[i][j]=lower_bound(X.begin(),X.end(),man[i][j])-X.begin();

int m=X.size(); // 情報の種類数
int s=n+m,t=s+1;
graph<int> G;
G.init(t+1);
// source to men
rep(i,n){
G.add_directed_edge(s,i,i!=tar?ub[i]:man[i].size());
}
// men to info
rep(i,n) rep(j,man[i].size()) {
G.add_directed_edge(i,n+man[i][j],1);
}
// info to sink
rep(i,m){
G.add_directed_edge(n+i,t,1);
}

printf("%d\n",Dinic(G,s,t));
}

return 0;
}

Dinic ライブラリは出し惜しみ。将来的には公開するかも。

K
#include<cstdio>
#include<cstring>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

void kmp_build(const char *pttn,int *fail){
int n=strlen(pttn);
fail[0]=-1;
for(int i=1,j=-1;i<=n;i++){
while(j>=0 && pttn[j]!=pttn[i-1]) j=fail[j];
fail[i]=++j;
}
}

int solve(const char *s,const char *pttn,const int *fail){
int m=strlen(s),n=strlen(pttn),j=0;

static int prev[512010],next[512010];
rep(i,m+1){
prev[i]=i-1;
next[i]=i+1;
}

int cnt=0;
static int hist[512010]; // hist[k] := ( i==k のときの j の値 )
rep(i,m){
while(j>=0 && s[i]!=pttn[j]) j=fail[j];
j++;
hist[i]=j;
if(j==n){
cnt++;
int pos=i;
rep(_,n){
next[prev[pos]]=next[pos];
prev[next[pos]]=prev[pos];
pos=prev[pos];
}
j=hist[pos];
}
}
return cnt;
}

int main(){
static char pttn[260],s[512010];
while(gets(pttn)&&gets(s)){
int fail[260];
kmp_build(pttn,fail);
printf("%d\n",solve(s,pttn,fail));
}
return 0;
}

スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。