Dwango2016 Finals

A:
おおっとりあえずメモ化探索しよ

#include<stdio.h>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
map<long long,int> dp;
vector<long long>hb;
long long calc(long long a){
	if(dp.count(a))return dp[a];
	long long best=a;
	for(int i=0;i<hb.size();i++){
		if(hb[i]>a)continue;
		long long cost=a%hb[i];
		if(cost>=best)continue;
		best=min(best,cost+calc(a/hb[i]));
	}
	return dp[a]=best;
}
int main(){
	long long a;scanf("%lld",&a);
	long long cur=0;
	for(int i=0;i<18;i++){
		cur*=10;
		if(i%2)cur+=2;
		else cur+=5;
		hb.push_back(cur);
	}
	cur=0;
	for(int i=0;i<18;i++){
		cur*=10;
		if(i%2)cur+=5;
		else cur+=2;
		hb.push_back(cur);
	}
	std::sort(hb.begin(),hb.end());
	printf("%lld\n",calc(a));
}

B:
壊れたドアと同じなのに変なこと考えてて駄目

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int b[1100];

int ABS(int a){
	return max(a,-a);
}
long long dp[1100][1100][2];
long long mod=1000000007;
long long inf=mod*mod;
long long calc(int a,int b,int c){
	if(dp[a][b][c]>=0)return dp[a][b][c];
	if(a==b)return inf;
	
}
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d",b+i);
	int pp=0;
	for(int i=0;i<a;i++)if(b[i]>0){pp=i;break;}
	if(pp==0){
		printf("1.00000000000\n");return 0;
	}
	double left=1;
	double right=2000000000.0;
	for(int i=0;i<100;i++){
		double M=(left+right)/2;
		for(int j=0;j<a;j++)for(int k=0;k<a;k++)for(int l=0;l<2;l++)dp[j][k][l]=inf;
		dp[pp][pp][0]=dp[pp][pp][1]=b[pp];
		dp[pp-1][pp-1][0]=dp[pp-1][pp-1][1]=-b[pp-1];
		for(int j=0;j<a-1;j++){
			for(int k=0;j+k<a;k++){
				for(int l=0;l<2;l++){
					int r=j+k;
					if(dp[k][r][l]==inf)continue;
					if(r<a-1){
						long long toc=dp[k][r][l];
						if(l==0)toc+=b[r+1]-b[k];
						else toc+=b[r+1]-b[r];
						if((double)toc/M<(double)ABS(b[r+1])){
							dp[k][r+1][1]=min(dp[k][r+1][1],toc);
						}
					}
					if(k){
						long long toc=dp[k][r][l];
						if(l==0)toc+=b[k]-b[k-1];
						else toc+=b[r]-b[k-1];
						if((double)toc/M<(double)ABS(b[k-1])){
							dp[k-1][r][0]=min(dp[k-1][r][0],toc);
						}
					}
				}
			}
		}
		long long ret=min(dp[0][a-1][0],dp[0][a-1][1]);
		if(ret<inf){
			right=M;
		}else left=M;
	}
	printf("%.12f\n",left);
}

C:
実 家 の よ う な 安 心 感

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int p[300000];
int q[300000];
int segtree[524288];
int query(int a,int b,int c,int d,int e){
	if(d<a||b<c)return 0;
	if(c<=a&&b<=d)return segtree[e];
	return max(query(a,(a+b)/2,c,d,e*2),query((a+b)/2+1,b,c,d,e*2+1));
}
void update(int a,int b){
	a+=262144;
	while(a){
		segtree[a]=max(segtree[a],b);
		a/=2;
	}
}
pair<pair<int,int> ,int> d[300000];
int z[300000];
int cnt[300000];
vector<int>lc[300000];
vector<pair<pair<int,int> ,int> >ev;
int y[300000];
int lq[300000];
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	
	for(int i=0;i<a;i++){
		scanf("%d%d",p+i,q+i);
		d[i]=make_pair(make_pair(q[i],-p[i]),i);
		z[i]=p[i];
	}
	z[a]=0;
	z[a+1]=b;
	d[a]=make_pair(make_pair(0,0),a);
	d[a+1]=make_pair(make_pair(c,-b),a+1);
	p[a+1]=b;
	q[a+1]=c;
	a+=2;
	std::sort(d,d+a);
	std::sort(z,z+a);
	for(int i=0;i<a;i++){
		int at=lower_bound(z,z+a,-d[i].first.second)-z;
	//	printf("%d\n",at);
		int val=0;
		if(at)val=query(0,262143,0,at-1,1);
		cnt[d[i].second]=val+1;
	//	printf("%d %d\n",d[i].second,val+1);
		update(at,val+1);
		
	}
	int lca=cnt[a-1];
	for(int i=0;i<524288;i++)segtree[i]=0;
	for(int i=a-1;i>=0;i--){
		int at=lower_bound(z,z+a,-d[i].first.second)-z;
		int val=0;
		val=query(0,262143,at+1,262142,1);
		if(cnt[d[i].second]+val==lca)lc[cnt[d[i].second]].push_back(d[i].second);
		update(at,val+1);
	}
	for(int i=0;i<=lca;i++){
	//	printf("%d: ",i);
	//	for(int j=0;j<lc[i].size();j++)printf("%d ",lc[i][j]);
	//	printf("\n");
	}
	long long ret=0;
	for(int i=0;i<295000;i++){
		if(lc[i].size()==0||lc[i+1].size()==0)continue;
		ev.clear();
		int sz=0;
		for(int j=0;j<lc[i].size();j++){
			ev.push_back(make_pair(make_pair(p[lc[i][j]],q[lc[i][j]]),0));
		}
		for(int j=0;j<lc[i+1].size();j++){
			ev.push_back(make_pair(make_pair(p[lc[i+1][j]],q[lc[i+1][j]]),1));
			y[sz++]=q[lc[i+1][j]];
		}
		std::sort(ev.begin(),ev.end());
		//for(int j=0;j<ev.size();j++)printf("%d %d %d %d %d\n",i,j,ev[j].first.first,ev[j].first.second,ev[j].second);
		std::sort(y,y+sz);
		int r=999999999;
		int ind=sz-1;
		int on=0;
		for(int j=0;j<ev.size();j++){
			if(ev[j].second==0){
				r=min(r,ev[j].first.second);
				on++;
			}else {ind--;on--;}
		//	printf("%d %d %d %d %d\n",i,j,r,ind,y[ind]);
			if(ind>=0&&j<ev.size()-1&&ev[j].first.first!=ev[j+1].first.first&&r<y[ind]){
				ret+=(long long)(ev[j+1].first.first-ev[j].first.first)/2*((y[ind]-r)/2);
			}
		}
		//printf("%lld\n",ret);
	}
	printf("%lld\n",ret);
}

D:
不可能


Dの部分点すら取れなかったけど2位でした。