スポンサーサイト

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

First Bangladeshi Contest of 2012-2013 Season

2012/07/07 18:00 ~ 23:00 (JST)
First Bangladeshi Contest of 2012-2013 Season

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

結果

A: -
B: -
C: AC
D: -
E: AC
F: -
G: -
H: AC
I: -
J: -
K: -
16/114

問題

問題セットの原文はここを参照。

B. Binary Substring (UVa 12472)

正整数 A, B, P が与えられるので、
・ A ≦ S ≦ P
・ 二進数表示したときに S は P を部分文字列として含む
をみたすような最小の S を求めよ。
存在しない場合はそれを指摘。

1 ≦ A, B, P ≦ 10^15
A ≦ B

C. Common Palindrome (UVa 12473)

文字列 A, B に部分列として含まれる最長共通回文の長さを求めよ。

( テストケース数 ) ≦ 100
|A|, |B| ≦ 60

E. Elliptic Athletics Track (UVa 12475)

整数 a, b が与えられる。
楕円 x^2/a^2 + y^2/b^2 = 1 の周長を求めよ。
絶対誤差または相対誤差で 10^(-5) 以下が許される。

H. Hardest Problem Ever (Easy) (UVa 12478)

名前の候補と文字が書かれたグリッドが与えられる。
一つの名前(のpermutation)だけ、グリッド内に二回現れる。そのほかの名前(のpermutation)は一回だけ現れる。
二回現れる名前を答えよ。

解答

B.
P の二進数表示が S の何桁目に埋まっているかを全探索。
何桁目かを固定したら、つまり S の一部の桁を固定したら、その条件下で A 以上最小の S は DFS で求められる。
digit DP の要領。( 実際はメモ化しないのでDPではないけど )
求まった S の中で最小のものが答え。

C.
A の区間と B の区間を状態にもつ素直な DP だと O(|A|^2 |B|^2) かかって、かなりあやしい。
なんとか計算量を落とそうとしたけど、どうにもならなかったのでその DP を書いてみたら TL 10sec のところ 9.9sec で通った。

E.
楕円積分をまじめに計算するのはめんどうなので、見た瞬間に検索ゲーだと思った。
Wikipedia にある公式は記号が意味不明だったので実装できなかった。
ここにいい感じのがあったので公式を借りてきて通した。
そのあと、同じ作者のさらにいい公式を見つけたので書き直した。下のコードはそれを使っている。

H.
output only。
目で見て探した。

ソースコード

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

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

using namespace std;

typedef long long ll;

const ll INF=1LL<<61;

int to_binary(ll a,char *s){
int i;
for(i=0;a>0;i++){
s[i]=a%2+'0';
a/=2;
}
return i;
}

// t の '?' を埋めて s 以上で最小の数を作る
ll dfs(const char *s,char *t,int i=54,bool b=false){ // b : 以降の桁を自由に決められるか
if(i==-1){
ll res=0;
rep(j,55) res|=(ll)(t[j]-'0')<<j;
return res;
}

if(t[i]=='?'){
if(b){
t[i]='0';
ll res=dfs(s,t,i-1,true);
t[i]='?';
return res;
}
else{
t[i]='1';
ll res=dfs(s,t,i-1,s[i]<t[i]);
if(s[i]=='0'){
t[i]='0';
res=min(res,dfs(s,t,i-1,false));
}
t[i]='?';
return res;
}
}
else{
if(b){
return dfs(s,t,i-1,true);
}
else{
if(s[i]<=t[i]){
return dfs(s,t,i-1,s[i]<t[i]);
}
else{
return INF;
}
}
}
}

void solve(){
ll a,b,p; scanf("%lld%lld%lld",&a,&b,&p);

char sa[64],sp[64];
int na=to_binary(a,sa);
int np=to_binary(p,sp);

for(;na<55;na++) sa[na]='0';

ll ans=INF;
rep(i,56-np){
char s[64]="???????????????????????????????????????????????????????";
rep(j,np) s[i+j]=sp[j];
ans=min(ans,dfs(sa,s));
}
if(ans<=b) printf("%lld\n",ans); else puts("NONE");
}

int main(){
int T,t; scanf("%d",&T);
for(t=1;t<=T;t++) printf("Case %d: ",t), solve();
return 0;
}


C.
#include<cstdio>
#include<cstring>
#include<algorithm>

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

using namespace std;

char s[77],t[77];

int dp[77][77][77][77];
int dfs(int i,int j,int k,int l){
if(i>j || k>l) return 0;

int &res=dp[i][j][k][l];
if(res!=-1) return res;

if(s[i]==s[j] && t[k]==t[l] && s[i]==t[k]){
return res=(i==j||k==l?1:2)+dfs(i+1,j-1,k+1,l-1);
}
return res=max(max(dfs(i+1,j,k,l),dfs(i,j-1,k,l)),
max(dfs(i,j,k+1,l),dfs(i,j,k,l-1)));
}

void solve(){
scanf("%s%s",s,t);
int m=strlen(s),n=strlen(t);
rep(j,m) rep(i,j+1) rep(l,n) rep(k,l+1) dp[i][j][k][l]=-1;
printf("%d\n",dfs(0,m-1,0,n-1));
}

int main(){
int T,t; scanf("%d",&T);
for(t=1;t<=T;t++) printf("Case %d: ",t), solve();
return 0;
}


E.
#include<cmath>
#include<cstdio>

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

using namespace std;

const double PI=acos(-1);

double ellipse_circumference(double a,double b){
int p[]={0,1,2,4,9,20,43,90,185,376,759,1526};
double c[]={5.9685,3.7127,0.28582,2.098,1.462,1.1413,0.736,0.459,0.244,0.144,0.051,0.062};
double h=pow((a-b)/(a+b),2),g=0;
rep(i,11) g+=c[i]*pow(h,p[i]);
return PI*(a+b)*(1+3*h/(10+sqrt(4-3*h))+(44-14*PI)/(11*PI)*pow(h,g));
}

void solve(){
int a,b; scanf("%d%d",&a,&b);
printf("%.9f\n",ellipse_circumference(a,b));
}

int main(){
int T,t; scanf("%d",&T);
for(t=1;t<=T;t++) printf("Case %d: ",t), solve();
return 0;
}


H.
#include<cstdio>

using namespace std;

int main(){
puts("KABIR");
return 0;
}

スポンサーサイト

コメントの投稿

非公開コメント

C

Cはdp[60][60][60][60]を取ってしまうとテーブルの初期化だけで時間がやばいです。
文字のポインタはl≦rなので、dp[60*60/2][60*60/2]という風に取ると初期化コストが安くなって、全く同じDPでも3.5sくらいで通ります。

Re: C

やったー! しめじたんからコメントもらった!

ループの順番が変なので読みにくいかもですが、初期化のところは 60*30*60*30 くらいになってるはずです。
三倍も速いのは不思議ですね。
再帰じゃなくてループで書きましたか?

No title

あ、よく見ると本当ですね。すみません。
memsetを使ったから速かったか、あるいはキャッシュにいっぱい乗ったとかなんでしょうか……


更新も終了条件も全く同じメモ化再帰のDPです。

Re: No title

なるほど。
memset が爆速だという話はたまに聞くので、それが原因なんだと思います。
アドバイスありがとうございます。
プロフィール

fura2

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

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

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