Atcoder Regular Contest #008 - DEGwerのブログ

ARC#8の参加記。

平成教育委員会を見ている。
8:00
家族がそのまま見ているので、見ながら始める。
A読む。サンプル読む。面倒なことは考えずにたこ焼き買う個数を動かそう。
00:02 AC.
B読む。普段より実装少なそう。
ちょっとバグバグする。
すぐに治る。
20:10 AC.
C読む。
ん？
わからないぞ!?
とりあえずD読む。
どう見ても座標圧縮+segtreeだよね。
(ax+b)c+d=acx+bc+dなので同型！やったぁ！各ノードにこれもっときゃいいね！
書く。
バグは少しだけ発生するがちゃんとサンプル通る。
20:46 WA(50点)
ファ!?なんで100点解実装してWAなのに50点取れてるの？
long long トラップでしたテヘペロ
20:48 AC.
C考える。
この辺で平成教育委員会が終わる。
うーん、やっぱりわからないなぁ、通してる人多いのになぁ...
dijkstraに気付く。
残り20分。実装開始(すでにこの前にグラフ構築は書いてある)。
O(V^2)のほうが速いのでそっちを書く。
実装終了。
21:17 CE
ファ!?
#includeを忘れてましたテヘペロ。VC++これしなくてもsqrtとか使えてよくない。
21:18 WA
distanceをsortするの忘れてましたテヘペロ。
21:20 AC.
全完。うれしい。
順位表見ると5位。わーい。
待機phaseしてたら6位になる。

そのまま終了。
6位は過去最高順位なのでうれしい。
Cのテストケースで「参加者があなただけなので配る必要がありません。」っていうのがあって例のあの問題を彷彿とさせてテストできなかった。

以下コード

#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
	int num;
	scanf("%d",&num);
	int mini=10000000;
	for(int i=num;i<=100;i++)
	{
		mini=min(mini,100*(i/10)+15*(i%10));
	}
	printf("%d\n",mini);
}

#include<stdio.h>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
int hai[26];
int mk[26];
int main()
{
	int na,nb;
	scanf("%d%d",&na,&nb);
	string mok,str;
	cin>>mok>>str;
	for(int i=0;i<str.size();i++)
	{
		hai[str[i]-'A']++;
	}
	for(int i=0;i<mok.size();i++)
	{
		mk[mok[i]-'A']++;
	}
	int maxi=0;
	bool han=false;
	for(int i=0;i<26;i++)
	{
		if(hai[i]!=0)
		{
			maxi=max(maxi,(mk[i]+hai[i]-1)/hai[i]);
		}
		else
		{
			if(mk[i]!=0)
			{
				han=true;
			}
		}
	}
	if(han)
	{
		printf("-1\n");
	}
	else
	{
		printf("%d\n",maxi);
	}
}

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
double map[1000][1000];
typedef pair<double,double>pdd;
double dis[1000];
bool flag[1000];
typedef pair<pdd,pdd>pd4;
int main()
{
	int num;
	scanf("%d",&num);
	vector<pd4>vec;
	for(int i=0;i<num;i++)
	{
		double za,zb,zc,zd;
		scanf("%lf%lf%lf%lf",&za,&zb,&zc,&zd);
		vec.push_back(make_pair(make_pair(za,zb),make_pair(zc,zd)));
	}
	for(int i=0;i<num;i++)
	{
		for(int j=0;j<num;j++)
		{
			map[i][j]=sqrt((vec[i].first.first-vec[j].first.first)*(vec[i].first.first-vec[j].first.first)+(vec[i].first.second-vec[j].first.second)*(vec[i].first.second-vec[j].first.second))/min(vec[i].second.first,vec[j].second.second);
		}
	}
	int now=0;
	fill(flag,flag+1000,false);
	fill(dis,dis+1000,100000000000000000000.0);
	dis[0]=0;
	for(int p=0;p<num-1;p++)
	{
		flag[now]=true;
		for(int i=0;i<num;i++)
		{
			dis[i]=min(dis[i],dis[now]+map[now][i]);
		}
		double mini=100000000000000000.0;
		int nn;
		for(int i=0;i<num;i++)
		{
			if(!flag[i])
			{
				if(dis[i]<mini)
				{
					mini=dis[i];
					nn=i;
				}
			}
		}
		now=nn;
	}
	double maxi=0;
	sort(dis+1,dis+num);
	for(int i=1;i<num;i++)
	{
		maxi=max(maxi,dis[i]+(num-1-i));
	}
	printf("%lf\n",maxi);
}

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<double,double>pdd;
typedef long long ll;
typedef pair<ll,pdd>pidd;
typedef pair<ll,ll>pii;
pdd seg[262144];
void update(int node,pdd a)
{
	node+=131072;
	seg[node]=a;
	for(;;)
	{
		node/=2;
		if(node==0)
		{
			break;
		}
		seg[node]=make_pair(seg[node*2].first*seg[node*2+1].first,seg[node*2].second*seg[node*2+1].first+seg[node*2+1].second);
	}
}
int main()
{
	int num,query;
	scanf("%d%d",&num,&query);
	vector<pidd>vec;
	vector<ll>prs;
	for(int i=0;i<131072;i++)
	{
		update(i,make_pair(1.0,0.0));
	}
	for(int i=0;i<query;i++)
	{
		ll za;
		double zb,zc;
		scanf("%lld%lf%lf",&za,&zb,&zc);
		vec.push_back(make_pair(za,make_pair(zb,zc)));
		prs.push_back(za);
	}
	sort(prs.begin(),prs.end());
	vector<ll>uni;
	ll now=-1;
	for(int i=0;i<query;i++)
	{
		if(now!=prs[i])
		{
			uni.push_back(prs[i]);
			now=prs[i];
		}
	}
	prs=uni;
	double maxi,mini;
	maxi=mini=seg[1].first+seg[1].second;
	for(int i=0;i<query;i++)
	{
		int low=lower_bound(prs.begin(),prs.end(),vec[i].first)-prs.begin();
		update(low,vec[i].second);
		maxi=max(maxi,seg[1].first+seg[1].second);
		mini=min(mini,seg[1].first+seg[1].second);
	}
	printf("%lf\n%lf\n",mini,maxi);
}

実装量が少なくて好きなセットでした。