GCJ R1-A

超低速2完で890位、ぎりぎり通過。わーい。
1-Bと1-Cに出る権利を失った。

A:「i文字目までのこす」場合を考えると、「i文字目までが全部あっている確率」*hoge+「i文字目までに誤りがある確率」*fugaの最小値を求めればよいことがわかる。
あとは実装。弱実装。

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	FILE *fp=fopen("a-large.in","r");
	FILE *fp2=fopen("out.txt","w");
	int data;
	fscanf(fp,"%d",&data);
	for(int i=1;i<=data;i++)
	{
		int ald,pas;
		fscanf(fp,"%d%d",&ald,&pas);
		vector<double>vec;
		for(int j=0;j<ald;j++)
		{
			double zan;
			fscanf(fp,"%lf",&zan);
			vec.push_back(zan);
		}
		double mini=1000000000.0;
		double rui=1.0;
		for(int k=0;k<ald;k++)
		{
			rui*=vec[k];
			mini=min(mini,rui*(pas-k+ald-k-1)+(1.0-rui)*(pas-k+ald-k+pas));
		}
		mini=min(mini,double(2+pas));
		fprintf(fp2,"Case #%d: ",i);
		fprintf(fp2,"%lf\n",mini);
	}
}

B:
level2のいずれか(要するに一番必要な力が小さいもの)がクリアできれば、それを行い、できなければlevel1でクリアできるもののうちlevel2で最後にクリアしそうなもの(=level2に必要な力が最大のもの)をクリアする、というぐりーでぃーでいける。
最初setをつかっており、同じ要素が現れる可能性を考えていなかったためバグる。multisetに書き直すとあっさり通る。

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
int main()
{
	FILE *fp=fopen("B-large.in","r");
	FILE *fp2=fopen("out.txt","w");
	int data;
	fscanf(fp,"%d",&data);
	for(int i=1;i<=data;i++)
	{
		printf("Case #%d: ",i);
		fprintf(fp2,"Case #%d: ",i);
		int num;
		fscanf(fp,"%d",&num);
		multiset<pair<int,int> >se;
		for(int j=0;j<num;j++)
		{
			int za,zb;
			fscanf(fp,"%d%d",&za,&zb);
			se.insert(make_pair(zb,za));
		}
		int ret=0;
		int now=0;
		multiset<pair<int,int> >::iterator it;
		multiset<pair<int,int> >::iterator it2;
		for(int k=0;k<num;k++)
		{
			it2=se.end();
			for(;;)
			{
				it=se.begin();
				pair<int,int>beg=*it;
				if(beg.first<=now)
				{
					se.erase(it++);
					now+=2;
					ret++;
					if(beg.second==1000000000)
					{
						now--;
					}
					break;
				}
				if(it2==se.begin())
				{
					printf("Too Bad\n");
					fprintf(fp2,"Too Bad\n");
					goto l01;
				}
				it2--;
				pair<int,int>zan=*it2;
				if(zan.second<=now)
				{
					now++;
					ret++;
					se.erase(it2++);
					se.insert(make_pair(zan.first,1000000000));
					it2=se.end();
				}
			}
		}
		printf("%d\n",ret);
		fprintf(fp2,"%d\n",ret);
l01:;
	}
}