※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「AOJ1051~1060」の編集履歴(バックアップ)一覧に戻る

AOJ1051~1060 - (2012/07/24 (火) 13:12:52) の編集履歴(バックアップ)


1052 Old Bridges

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1052&lang=jp
島を結ぶ吊り橋を渡って全部の財宝を回収しながら最初の島に戻ることができるかを判断する問題。

強度の低いつり橋から回収して試していくだけの一番簡単な部類の問題です。
この問題普通は0.0000秒のコード実行時間(早すぎて計測不可能)で解くのが普通なのですが一人だけ0.0032秒かつ大量のメモリーをつかって解いてる方がいました。
25!なわけはありませんしメモ化や動的計画法にしてはメモリを大量消費しています。
どのような手法で解いたのか逆に気になるところです。



#include<stdio.h>
#include<algorithm>
struct State{
int a,b;
bool operator<(const State& s)const{
	return b<s.b;
}
};
int main(){
int n,sum;
State ss[26];
while(1){
	scanf("%d",&n);
	if(n==0)break;
	for(int i=0;i<n;i++)scanf("%d %d",&ss[i].a,&ss[i].b);
	std::sort(ss,ss+n);
	sum=0;
	for(int i=0;i<n;i++){
		sum+=ss[i].a;
		if(sum>ss[i].b){
			sum=-1;
			break;
		}
	}
	printf("%s\n",sum==-1?"No":"Yes");
}
}


1056 Ben Toh

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1056&lang=jp
最大10万日にわたる弁当争奪戦でどれだけ弁当をゲットできるか期待値を求める問題。

この問題賢い漸化式を建てようとすると計算量との戦いで中々漸化式が立ちません。
漸化式が立っても計算量が膨れ上がったりして何度も式変形を投げました。
なのですがこの問題不思議なことに、日数がたつごとに前日からの弁当取得数期待値の増加が定数に収束します。
そこを利用して適当な日までは厳密に計算し後は単純な線形予測で解けます。

追記
さて問題も解けたので他の回答者のコードを覗いてみました。
この問題線形予測で解いている方とメモ化計算で解いてる方に分かれるようです。
メモ化のほう今から勉強です、漸化式立つのかこの問題、勉強になるなあ。




#include<stdio.h>
long double memo[32];
double saiki(int deep,long double r1,long double r2,long double sum,int last){
if(deep==last){
	return sum*r2;
}
double re=0;
if(deep>0)re=(1.0-r1)*(memo[last-deep-1]+sum)*r2;
re+=saiki(deep+1,r1*0.5,r2*r1,sum+1,last);//弁当をゲットできた
return re;
}
int main(){
for(int i=1;i<31;i++){
	memo[i]=saiki(0,1.0,1.0,0,i);
	//printf("%.13Lf\n",memo[i]);
}
long double add=0.621446216664598;//30日目以降はこの値で取得数が増えていくと考えても誤差累積は小さく何の問題もない
int n;
while(1){
	scanf("%d",&n);
	if(n==0)break;
	if(30<n) printf("%Lf\n",memo[30]+(n-30)*add);
	else printf("%Lf\n",memo[n]);
}
}