「AOJ1051～1060」の編集履歴（バックアップ）一覧に戻る
AOJ1051～1060 - (2013/01/14 (月) 01:37:33) のソース
*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");
}
}
*1053 Accelerated Railgun
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1053&lang=jp
超能力者が協力して研究所を爆破できるかを問う問題。
この問題はD<50という意味不明なデータがかなり疑問な問題です。
円周は入射角＝反射角なのだから最初の射出方向を含む直線上に研究所がなければ話になりません。
条件を満たすのは円を２等分する直線しかないわけです。
多分D<50によって何か複雑な動きで当たる場合もあるのではと勘違いさせるひっかけ問題を考えたのでしょうか？
ベクトルの外積を使ってまずは研究所と射出方向のベクトルが同じ向きか反対向き出ないか調べます。
次に内積を使って円の外、円のうちどちら向きに発射したかを求めます。
#include<stdio.h>
#include<math.h>
int main(){
double d,px,py,vx,vy,len;
while(1){
scanf("%lf",&d);
if(d==0.0)break;
scanf("%lf %lf %lf %lf",&px,&py,&vx,&vy);
if(px*vy-py*vx==0.0){
if(px*vx+py*vy>=0){
//研究所と反対方向に射出した
len=2.0-sqrt(px*px+py*py);
}else{
len=sqrt(px*px+py*py);
}
if(d>=len)printf("%.8lf\n",len);
else printf("impossible\n");
}else{
printf("impossible\n");
}
}
}
*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]);
}
}
*問い1060
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1060
最小公倍数がＬとなるa,b(a<=b)となる自然数の組の数を答える問題。
解法
C=lcm(a,b)としますと
a=p1^a1*p2^a2*,,*pn^an
b=q1^b1*q2^b2*,,*qn^bn
とa,bを素因数分解したとき
piとqjが同じならCの素因数分解はaiとbjの大きい方をｃとしてCの素因数のpi^c,piがqiにないならpi^aiがｃの素因数となり、qiがpiにないならqi^biがCの素因数となります。
後はこの組み合わせを全部試して、最後にa<=bの組み合わせを見るだけです。
#include<stdio.h>
#include<iostream>
#include<map>
#include<math.h>
long long int ans=0;
std::map<long long int,int> memo;
void search(long long int a,long long int b,std::map<long long int,int>::iterator it){
if(it==memo.end()){
ans++;
return ;
}
long long int m=1,r=1;
for(int i=0;i<(*it).second;i++)m*=(*it).first;
for(int i=0;i<=(*it).second;i++){
it++;
search(a*r,b*m,it);
if(m!=r)search(a*m,b*r,it);
it--;
r*=(*it).first;
}
}
void calc(long long int n){
memo.clear();
ans=0;
long long int num=n,mult;
for(long long int i=2;i*i<=n;i+=(i&1)+1){
int count=0;
while(n%i==0){
n/=i;
count++;
}
if(count>0)memo[i]=count;
}
if(n!=1){
if(memo.find(n)==memo.end())memo[n]=0;
memo[n]+=1;
}
if(num==1){
ans=1;
}else{
search(1,1,memo.begin());
ans=(ans+1)/2;
}
}
int main(){
long long int n;
while(1){
std::cin>>n;
if(n==0)break;
calc(n);
std::cout<<ans<<"\n";
}
}
