スポンサーサイト

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

Another Bangladeshi Contest

2012/10/06 四時間。
難しめ。Uva のコンテストは解説がなくて復習できないのが困る。
このセットについては、laycurse さんが動画を公開してくれているので助かる。

Tags : プログラミング UVa 未解決

結果

8 問中 A, C, E の3 問解いて 17 位。
解けなかった中で正解数が多かった B と F を考えていたけど、B はできそうでできなくて、F はまるでわからなかった。

問題

A. Distinct Substring (UVa 12494)
文字列 S が与えられる。S の部分文字列は何種類あるか?
ここで、二つの文字列 S1, S2 が等しいとは、S1 のある cyclic permutation が S2 に一致することとする。

1 ≦ テストケース数 ≦ 50
1 ≦ |S| ≦ 200

B. 'C' for Count (UVa 12495)
円形に配置された N 個のいすに K 人が座る方法は何通りあるか? mod 10^9+7 で求めよ。
ただし、どの二人も間隔が D 以上空いていないといけない。

1 ≦ テストケース数 ≦ 5000
1 ≦ K ≦ N ≦ 1000
1 ≦ D ≦ 10

C. Fisherman's Dilemma (UVa 12496)
n × m のグリッドの各マスに 20 以下の正整数が書かれている。
グリッドの部分長方形を ( すべての選び方の中から等確率に ) 選んで、その長方形内の数字の和が K 以上になる確率はいくらか? 既約分数で答えよ。

1 ≦ テストケース数 ≦ 50
1 ≦ n, m ≦ 200

E. Ant's Shopping Mall (UVa 12498)
R × C のグリッドがあり、各マスは障害物があるかないかのいずれか。
どこでもいいので一列を選んで、その列には障害物が一つもないようにしたい。
障害物を移動するには、左右にのみ移動できて、一マス移動させるごとにコストが 1 かかる。
また、移動先に障害物がある場合は移動できない。
最小コストを求めよ。どうやっても目標を達成できないなら -1。

1 ≦ テストケース数 ≦ 50
2 ≦ R ≦ 50
1 ≦ C ≦ 50

解答

A.
A だし全探索かと思って書き出しそうになったけど、冷静になると全然間に合わないのでちょっと工夫する。
部分文字列を全列挙するのはよくて、その部分文字列の O(|S|) 通りある rotation のうち、hash 値が最小のものだけを保存しておく。これは rolling hash を使えば O(|S|) でできて、全体で O(|S|^3) で解ける。

B.
解けなかったので、小さいケースを全探索して、その結果を元に OEIS を駆使して漸化式を見つけた。
漸化式は二項係数と全く同じで、初期条件だけが D に依存して変わる。
なんでこうなるのか誰か教えてください…
全部前計算しておいて、クエリは O(1) で処理した。
計算量は O(NKD)。
O(NK) 解法もあるらしい。気になる。

C.
部分長方形の総数は簡単に求められるので、和が K 以上になる長方形の個数を求める問題になる。

まず、累積和の DP をして長方形内の和を O(1) で引けるようにする。
長方形の上端と下端について全探索。
x 方向については尺取る。
計算量は O(n^2・m) となり間に合う。

E.
サイズが小さいので、単純にすべての列について試せばいい。
コストの計算がちょっとだけめんどう。

ソースコード

A.
#include<set>
#include<cstdio>
#include<cstring>

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

using namespace std;

typedef long long ll;

ll hash(int n,const char *s){
const ll P=1000000007;

ll Ppow=1;
rep(i,n) Ppow*=P;

ll h=0;
rep(i,n) h=h*P+s[i];
ll res=h;
rep(i,n){
res=min(res,h);
h*=P;
h-=Ppow*s[i];
h+=s[i];
}
return res;
}

int main(){
int T; scanf("%d",&T);
while(T--){
char s[256]; scanf("%s",s);
int n=strlen(s);

set<ll> S;
rep(i,n) for(int j=i;j<n;j++) {
int len=j-i+1;
S.insert(hash(len,s+i));
}
printf("%d\n",S.size());
}

return 0;
}


B.
#include<cstdio>
#include<algorithm>

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

using namespace std;

const int M=1000000007;

int main(){
static int dp[10][1001][1001];
for(int d=1;d<=10;d++){
rep(n,1001) dp[d-1][n][0]=(n==0?d:1);
rep(n,1000) rep(r,n+1) dp[d-1][n+1][r+1]=(dp[d-1][n][r+1]+dp[d-1][n][r])%M;
}

int T; scanf("%d",&T);
for(int cas=1;cas<=T;cas++){
int n,k,d; scanf("%d%d%d",&n,&k,&d);
printf("Case %d: %d\n",cas,k==1?n:dp[d-1][max(n-(d-1)*k,0)][k]);
}

return 0;
}


C.
#include<cstdio>

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

using namespace std;

int gcd(int a,int b){ return b?gcd(b,a%b):a; }

int main(){
int T; scanf("%d",&T);
for(int cas=1;cas<=T;cas++){
int h,w,K; scanf("%d%d%d",&h,&w,&K);
static int a[200][200];
rep(i,h) rep(j,w) scanf("%d",a[i]+j);

static int sum[201][201];
rep(i,h) rep(j,w) sum[i+1][j+1]=sum[i+1][j]+sum[i][j+1]-sum[i][j]+a[i][j];

int cnt=0;
rep(i1,h) for(int i2=i1+1;i2<=h;i2++) {
for(int j1=0,j2=1;j1<w;j1++){
while(j2<=w && sum[i2][j2]-sum[i2][j1]-sum[i1][j2]+sum[i1][j1]<K) j2++;
cnt+=w+1-j2;
}
}

int cnt2=h*(h+1)/2*w*(w+1)/2;
int g=gcd(cnt,cnt2);
printf("Case %d: %d/%d\n",cas,cnt/g,cnt2/g);
}

return 0;
}


E.
#include<cstdio>
#include<algorithm>

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

using namespace std;

const int INF=1<<29;

int main(){
int T; scanf("%d",&T);
for(int cas=1;cas<=T;cas++){
int h,w; scanf("%d%d",&h,&w);
static char B[50][51];
rep(i,h) scanf("%s",B[i]);

int ans=INF;
rep(j,w){
int cnt=0;
rep(i,h) if(B[i][j]=='1') {
bool ok=false;
int left=0;
for(int k=j-1;k>=0;k--){
left++;
if(B[i][k]=='0'){ ok=true; break; }
}
if(!ok) left=INF;

ok=false;
int right=0;
for(int k=j+1;k<w;k++){
right++;
if(B[i][k]=='0'){ ok=true; break; }
}
if(!ok) right=INF;

cnt+=min(left,right);
if(cnt>=INF) break;
}

ans=min(ans,cnt);
}
if(ans==INF) ans=-1;

printf("Case %d: %d\n",cas,ans);
}

return 0;
}

スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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