スポンサーサイト

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

X Programming Olympiads in Murcia (Spain)

2012/05/05
X Programming Olympiads in Murcia (Spain)

制約が書いてない問題が複数あったのが残念だった。

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

問題

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

B. Bars (UVa 12455)

整数が p 個与えられる。
それらの部分集合を選んで、選んだ数の和がちょうど n にできるかどうか判定せよ。

1 ≦ p ≦ 20
0 ≦ n ≦ 1000

C. Mirror codes (UVa 12456)

長さ d の整数列 a[1] a[2] a[3] ... a[d] が与えられる。
長さ d の整数列 b[1] b[2] b[3] ... b[d] であって、
・ 0 ≦ b[i] ≦ a[i] ( i = 1, 2, ..., d )
・ 数列 b[d] b[d-1] ... b[1] は b[1] b[2] ... b[d] と一致しない
をみたすものは何通りあるか。
答えは 32 bit int に収まる。

D. Tennis contest (UVa 12457)

n 本先取のゲームで、一本あたりの自分の勝つ確率は p、負ける確率は 1-p とする。
自分がゲームに勝つ確率を求めよ。

1 ≦ n ≦ 25

E. Oh, my trees! (UVa 12458)

二分探索木から辺が消えたものが与えられる。
すなわち、各頂点に割り当てられた数字とその高さがわかっている。
このとき、元の二分探索木を復元せよ。

F. Bees' ancestors (UVa 12459)

メスの蜂には両親がいる。
オスの蜂には母親だけがいる。
一匹のオスの蜂からはじめて、n 世代前には何匹の蜂がいるか?

1 ≦ n ≦ 80

G. Careful teacher (UVa 12460)

20000 文字以下からなる辞書が与えられる。
二つの文字列 s, t が与えられる。
s の一文字を変化させることを繰り返して t に一致させられるか判定せよ。
ただし、変化後の文字列は辞書に入っていないといけない。

解答

A.
問題文が意味不明 ( 何を求めてほしいのかわからない ) ので解く気がない。

B.
ただの部分和問題。
O(p・2^p) の全探索で解いた。
DP すれば O(2^p) に落とせる。
また、n が小さいのでその方向に DP すれば O(p・n) くらいでもできる。
#include<cstdio>

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

using namespace std;

int main(){
int T; scanf("%d",&T);
while(T--){
int tar,n; scanf("%d%d",&tar,&n);
int a[20];
rep(i,n) scanf("%d",a+i);

bool ok=false;
rep(S,1<<n){
int sum=0;
rep(i,n) if(S&1<<i) sum+=a[i];
if(sum==tar){ ok=true; break; }
}

puts(ok?"YES":"NO");
}

return 0;
}


C.
反転して一致する文字列の個数を全体から引けばいい。
反転して一致する文字列は、ようするに左半分だけを自由に決められるということなので、かけざんで個数を計算できる。
#include<cstdio>
#include<vector>

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

using namespace std;

typedef long long ll;

int main(){
for(int n;scanf("%d",&n),n;){
vector<int> base(n);
rep(i,n) scanf("%d",&base[i]);

ll ans1=1,ans2=1;
rep(i,n){
ans1*=base[i];
if(i<(n+1)/2) ans2*=min(base[i],base[n-i-1]);
}
printf("%lld\n",ans1-ans2);
}

return 0;
}


D.
出力が小数以下二桁でいいので、モンテカルロでいけるだろうと思ってやったら、本当に通った。
がんばればかっちり数式でも求められると思う。
#include<cstdio>
#include<climits>

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

using namespace std;

unsigned xor32(){
static unsigned x=123456789,y=362436069,z=521288629,w=88675123;
unsigned t=x^(x<<11);
x=y; y=z; z=w;
return w=(w^(w>>19))^(t^(t>>8));
}

int main(){
int T; scanf("%d",&T);
while(T--){
int n;
double p; scanf("%d%lf",&n,&p);

int win=0;
rep(t,100000){
int a=0,b=0;
while(a<n && b<n){
if(xor32()<p*UINT_MAX) a++; else b++;
}
if(a==n) win++;
}
printf("%.2f\n",win/1e5);
}

return 0;
}


E.
制約が書いていないせいで悪問になってしまった。
問題自体はおもしろい。

根に近い数から順に、本当に二分探索木に記録していく方法では TLE した。
木が平衡していない場合、最悪 O(V^2) かかる。

各深さの頂点について、どの範囲の数字がその頂点の子になるかというのを根に近いところから計算していく DP をしたら通った。
計算量はよくわからないけど、O(V^2) よりいい評価は出せる気がする。

制約がわからないので vector< vector<hoge> > とか書かないといけなくてストレスフルだった。
#include<cstdio>
#include<vector>

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

using namespace std;

const int INF=1<<30;

template<class T>
struct interval{ T a,b; };

bool cover(const interval<int> &I,int data){
return I.a<=data && data<=I.b;
}

int main(){
int T; scanf("%d",&T);
while(T--){
int h; scanf("%d ",&h);
vector< vector<int> > data(h);
rep(i,h){
static char s[100000]; gets(s);
for(int j=0,a=0;;j++){
if(s[j]==' ' || s[j]=='\0'){
if(j==0 || s[j-1]==' ') continue;
data[i].push_back(a);
a=0;
if(s[j]=='\0') break;
}
else a=10*a+(s[j]-'0');
}
}

vector< vector<int> > L(h),R(h); // answer
vector< vector< interval<int> > > I(h);
rep(i,h){
L[i].assign(data[i].size(),INF);
R[i].assign(data[i].size(),INF);
I[i].assign(data[i].size(),(interval<int>){-INF,INF});
}
for(int i=1;i<h;i++){
rep(j,data[i].size()){
int a=data[i][j];
rep(k,data[i-1].size()) if(cover(I[i-1][k],a)) {
if(a<data[i-1][k]) L[i-1][k]=a, I[i][j]=(interval<int>){I[i-1][k].a,data[i-1][k]-1};
else R[i-1][k]=a, I[i][j]=(interval<int>){data[i-1][k]+1,I[i-1][k].b};
}
}
}

rep(i,h) rep(j,data[i].size()) {
printf("%d:",data[i][j]);
if(L[i][j]!=INF) printf("%d",L[i][j]);
putchar('-');
if(R[i][j]!=INF) printf("%d",R[i][j]);
putchar('\n');
}
}

return 0;
}


( TLE 解 )
二分探索木のスマートな書き方を知らないのでポインタポインタとか使ってしまった。
#include<cstdio>
#include<vector>
#include<cstdlib>

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

using namespace std;

struct binary_search_tree{
struct node{
int data;
node *l,*r;
node(int data):data(data),l(NULL),r(NULL){}
};
node *root;

binary_search_tree():root(NULL){}

void add(int data){
node **u=&root;
while(*u){
if(data<(*u)->data) u=&((*u)->l);
else u=&((*u)->r);
}
*u=(node *)malloc(sizeof(node));
**u=node(data);
}

const node *search(int data){
node *u=root;
while(data!=u->data){
if(data<u->data) u=u->l;
else u=u->r;
}
return u;
}
};

int main(){
int T; scanf("%d",&T);
while(T--){
vector<int> data;
int h; scanf("%d ",&h);
rep(i,h){
static char s[100000]; gets(s);
for(int i=0,a=0;;i++){
if(s[i]==' ' || s[i]=='\0'){
if(i==0 || s[i-1]==' ') continue;
data.push_back(a);
a=0;
if(s[i]=='\0') break;
}
else a=10*a+(s[i]-'0');
}
}

binary_search_tree B;
rep(i,data.size()) B.add(data[i]);
rep(i,data.size()){
const binary_search_tree::node *u=B.search(data[i]);
printf("%d:",data[i]);
if(u->l) printf("%d",u->l->data);
putchar('-');
if(u->r) printf("%d",u->r->data);
putchar('\n');
}
}

return 0;
}


F.
典型的な Fibonacci 数列。
Fibonacci の F。
#include<cstdio>

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

using namespace std;

typedef long long ll;

int main(){
ll f[81]={0},m[81]={1};
rep(i,80){
f[i+1]=f[i]+m[i];
m[i+1]=f[i];
}

for(int n;scanf("%d",&n),n;) printf("%lld\n",f[n]+m[n]);

return 0;
}


G.
文字列は比較のコストが重いので、ローリングハッシュで全部 64bit int にしてしまう。
与えられる文字列の長さが全部等しいかどうかがわからなかったので、それもちゃんと管理した。
始点の文字列からふつうに BFS する。
辞書をあらかじめソートしておくと、ある文字列が辞書に含まれるかどうかは、二分探索で O(log n) ( n は単語数 ) で出せる。

これも文字列長の上限が書いていなくて、cin や string を使わざるを得ず、ストレスフルだった。
#include<queue>
#include<string>
#include<iostream>
#include<algorithm>

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

using namespace std;

typedef long long ll;

const ll P1=131;
const ll P2=1000000007;

ll P1k[100000]; // P1^k mod P2

struct hashed{
int len;
ll h;
hashed(){}
hashed(const string &s){
len=s.length();
h=0;
rep(k,len) h+=s[k]*P1k[k];
h%=P2;
}
bool operator<(const hashed &H)const{ return len<H.len || len==H.len && h<H.h; }
bool operator==(const hashed &H)const{ return len==H.len && h==H.h; }
bool operator!=(const hashed &H)const{ return !(*this==H); }
};

int main(){
P1k[0]=1;
rep(k,99999) P1k[k+1]=P1k[k]*P1%P2;

vector<string> dic_s;
while(1){
string s; cin>>s;
if(s=="--") break;
dic_s.push_back(s);
}
int n=dic_s.size();

vector<hashed> dic(n);
rep(i,n) dic[i]=hashed(dic_s[i]);

vector< pair<hashed,string> > tmp(n);
rep(i,n) tmp[i]=make_pair(dic[i],dic_s[i]);
sort(tmp.begin(),tmp.end());
rep(i,n){
dic[i]=tmp[i].first;
dic_s[i]=tmp[i].second;
}

while(1){
string s0,t0;
if(!(cin>>s0>>t0)) break;

hashed s(s0),t(t0);
int id_s=lower_bound(dic.begin(),dic.end(),s)-dic.begin();
int id_t=lower_bound(dic.begin(),dic.end(),t)-dic.begin();
if(id_s==n || dic[id_s]!=s || id_t==n || dic[id_t]!=t){
cout<<"No"<<endl;
continue;
}

vector<bool> vis(n);
vis[id_s]=true;

bool ans=false;
queue<int> Q; Q.push(id_s);
while(!Q.empty()){
int id=Q.front(); Q.pop();

if(id==id_t){ ans=true; break; }

rep(c,128) if(isprint(c)) rep(k,dic[id].len) {
hashed H=dic[id];
H.h+=(c-dic_s[id][k])*P1k[k];
H.h%=P2;
if(H.h<0) H.h+=P2;

int id2=lower_bound(dic.begin(),dic.end(),H)-dic.begin();
if(id2<n && dic[id2]==H && !vis[id2]){
vis[id2]=true;
Q.push(id2);
}
}
}

cout<<(ans?"Yes":"No")<<endl;
}

return 0;
}

スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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