JOI 春合宿 2010 Day 2

はい、2日目。

足し算

繰り上がりがあって、和が10を超えない時
繰り上がりがあって、和が10を超える時
繰り上がりがなくて、和が10を超えない時
繰り上がりがなくて、和が10を超える時
に場合分けしてやった。
最後に残った繰り上がりの1を忘れていてWAをはいて、
それを治したらWAで80点になった。
そこから色々ミス探したけど見つからず。
終了後に実際のテストケースで試したらセグフォしたので、配列の大きさが足りてないだけだとわかった。ほんまにキレそう。腹たつ。こんなミスした自分に腹立つ。

int m,M;
int a[20100],A[20100];
ll l[20100],L[20100];
int dig[80100];
ll num[80100];
int main()
{
	scanf("%d",&m);
	rep(i,m)scanf("%d %lld",&a[i],&l[i]);
	scanf("%d",&M);
	rep(i,M)scanf("%d %lld",&A[i],&L[i]);
	reverse(l,l+m);
	reverse(a,a+m);
	reverse(A,A+M);
	reverse(L,L+M);
	l[m]=INF;
	L[M]=INF;
	int cnt1=0,cnt2=0,k=0,ans_id=0;
	while(cnt1<m||cnt2<M)
	{
		int p = min(l[cnt1],L[cnt2]);
		if(k&&a[cnt1]+A[cnt2]+k<10)
		{
			dig[ans_id]=a[cnt1]+A[cnt2]+k;
			num[ans_id++]=1;
			l[cnt1]--;
			L[cnt2]--;
			if(l[cnt1]==0)cnt1++;
			if(L[cnt2]==0)cnt2++;
			k=0;
		}
		else if(k&&a[cnt1]+A[cnt2]+k>=10)
		{
			dig[ans_id]=(a[cnt1]+A[cnt2]+k)%10;
			num[ans_id++]=min(l[cnt1],L[cnt2]);
			l[cnt1]-=p;
			L[cnt2]-=p;
			if(l[cnt1]==0)cnt1++;
			if(L[cnt2]==0)cnt2++;
			k=1;
		}
		else if(a[cnt1]+A[cnt2]<10)
		{
			dig[ans_id]=a[cnt1]+A[cnt2];
			num[ans_id++]=min(l[cnt1],L[cnt2]);
			l[cnt1]-=p;
			L[cnt2]-=p;
			if(l[cnt1]==0)cnt1++;
			if(L[cnt2]==0)cnt2++;
		}
		else
		{
			dig[ans_id]=(a[cnt1]+A[cnt2])%10;
			num[ans_id++]=1;
			dig[ans_id]=(a[cnt1]+A[cnt2]+1)%10;
			num[ans_id++]=p-1;
			l[cnt1]-=p;
			L[cnt2]-=p;
			if(l[cnt1]==0)cnt1++;
			if(L[cnt2]==0)cnt2++;
			k=1;
		}
	}
	if(k)
	{
		dig[ans_id]=1;
		num[ans_id++]=1;
	}
	vector<P> ans;
	rep(i,ans_id)
	{
		if(num[i]==0)continue;
		if(!ans.empty()&&dig[i]==ans.back().fi)ans[(int)ans.size()-1].sec+=num[i];
		else ans.pb(P(dig[i],num[i]));
	}
	while(!ans.empty()&&ans.back().fi==0)ans.pop_back();
	reverse(all(ans));
	printf("%d\n",(int)ans.size());
	rep(i,ans.size())printf("%d %lld\n",ans[i].fi,ans[i].sec);
	return 0;
}

DNAの合成

普通にDP。文字列が一致してるかどうかの判定はロリハでする。
毎回ハッシュ求めてたら遅いので順番に求めてやる。
定数20は重い。

const ull B = 1000000007ull;
ull hash(string s,int a,int b)
{
	ull res = 0ull;
	for(int i=a;i<a+b;i++)
	{
		res *= B;
		res += s[i]-'A'+4;
	}
	return res;
}
int dp[150100];
int N;
vector<ull> dna;
string target;
ull BB[30];
int main()
{
	BB[0]=1ll;
	for(int i=1;i<30;i++)BB[i]=BB[i-1]*B;
	scanf("%d",&N);
	cin >> target;
	rep(i,N)
	{
		string s;
		cin >> s;
		dna.pb(hash(s,0,(int)s.size()));
	}
	SORT(dna);
	dp[0]=0;
	for(int i=1;i<=(int)target.size();i++)dp[i]=INF;
	ull h=0ull;
	for(int i=1;i<=(int)target.size();i++)
	{
		h*=B;
		h+=target[i-1]-'A'+4;
		if(binary_search(all(dna),h))dp[i]=1;
	}
	for(int i=2;i<=(int)target.size();i++)
	{
		int t = INF;
		h = target[i-1]-'A'+4;
		for(int j=2;j<=20;j++)
		{
			if(i-j<0)break;
			h += BB[j-1]*(target[i-j]-'A'+4);
			t = min(t,dp[i-j+1]);
			if(binary_search(all(dna),h))dp[i]=min(dp[i],t+1);
		}
	}
	printf("%d\n",dp[(int)target.size()]);
	return 0;
}

地域

木の直径って書いてあったので、木DPかな?と思ったけどNが結構でかいので違うなぁと踏む。
最大値の最小値だしどうせにぶたんでしょ、と思って判定を考えた。
葉から順に直径がX以下になるように切っていって、最終的に切った回数がM未満ならOKだと考えて、嘘臭いなぁと思いつつとりあえず書いて投げたら通ってしまった。(解法が正しいことはあとで解説読んで確認するつもりです)

int N,M;
struct edge
{
	int to,cost;
	edge(int to,int cost):to(to),cost(cost){}
};
vector<edge> g[30100];
int X,divide;
int dfs(int v,int p)
{
	vector<int> vec;
	for(int i=0;i<g[v].size();i++)
	{
		edge e = g[v][i];
		if(e.to==p)continue;
		int f = dfs(e.to,v)+e.cost;
		if(f<=X)vec.pb(f);
		else divide++;
	}
	if(vec.empty())return 0;
	sort(all(vec),greater<int>());
	int i;
	for(i=0;i<(int)vec.size()-1;i++)
	{
		if(vec[i]+vec[i+1]>X)divide++;
		else break;
	}
	if(i==(int)vec.size()-1)return vec[(int)vec.size()-1];
	return vec[i];
}
int main()
{
	scanf("%d %d",&N,&M);
	for(int i=0;i<N-1;i++)
	{
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		a--;b--;
		g[a].pb(edge(b,c));
		g[b].pb(edge(a,c));
	}
	int l=-1,r=INF;
	while(r-l>1)
	{
		int mid = (l+r)/2;
		X = mid;
		divide = 0;
		dfs(0,-1);
		if(divide>=M)l=mid;
		else r = mid;
	}
	printf("%d\n",r);
	return 0;
}

80+100+100 = 280
こんなミスで満点取れなかったの悔しすぎる。
本番だったら20点で代表になれるかどうか左右されるのにこんなんじゃまずいのでもっと問題解きまくります。
期末が近づいてきてるらしいけどしらん。
ここまで 580/600
頑張ろう。