tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

Codeforces Round #373 (Div. 1)

紫コーダーはDiv1のwriterやるのやめてほしい。

A B C D E Place
00:13 削除*1 01:02 -4 - 42th

A:
一番左に出てきた5を四捨五入していく。ひどい実装問題。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
char in[210000];
char str[210000];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	scanf("%s",in);
	int ind=0;
	int sz=0;
	for(int i=0;i<a;i++){
		if(in[i]=='.')ind=i;
		else str[sz++]=in[i];
	}
	int one=0;
	for(int i=0;i<sz;i++){

		if(i>=ind&&str[i]>='5'&&str[i]<='9'){
			int at=i;
			while(b--){
				if(at<ind)break;
				if(str[at]>='5'&&str[at]<='9'){
					if(at==0){
						one++;
					}else{
						str[at-1]++;
						int t=at-1;
						while(str[t]>'9'){
							str[t]-=10;
							if(t==0){
								one=1;break;
							}
							else str[t-1]++;
							t--;
						}
					}
				}else break;
				sz=at;
				at--;
			}
			break;
		}
	}
	
	while(sz>ind){
		if(str[sz-1]=='0')sz--;
		else break;
	}
	if(one)printf("1");
	for(int i=0;i<sz;i++){
		if(i==ind)printf(".");
		printf("%c",str[i]);
		
	}printf("\n");
}

B:
(^_^;)

C:
例の区間加算と区間和のsegtreeで行列やベクトルで値を持つ。こんな実装をする前に行列やベクトルのライブラリを用意すべきである。それにしても全く面白くない問題。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
struct mat{
	long long t[2][2];
	mat(){t[0][0]=t[0][1]=t[1][0]=t[1][1]=0;}
};

mat seg1[262144];
bool flag[262144];
long long seg2[262144][2];
int p[110000];
mat tmp;
mat I;
mat F(int a){
	mat ret;
	mat val;
	ret.t[0][0]=ret.t[1][1]=1;
	val.t[0][0]=val.t[0][1]=val.t[1][0]=1;
	while(a){
		if(a%2){
			for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=0;
			for(int k=0;k<2;k++)for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=(tmp.t[i][j]+ret.t[i][k]*val.t[k][j])%mod;
			for(int i=0;i<2;i++)for(int j=0;j<2;j++)ret.t[i][j]=tmp.t[i][j];
		}
		a/=2;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=0;
		for(int k=0;k<2;k++)for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=(tmp.t[i][j]+val.t[i][k]*val.t[k][j])%mod;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)val.t[i][j]=tmp.t[i][j];
	}
	return ret;
}
long long t2[2];
void add(int a,int b,int c,int d,int e,mat f){
	if(d<a||b<c)return;
	if(c<=a&&b<=d){
		flag[e]=true;
		t2[0]=seg2[e][0]*f.t[0][0]+seg2[e][1]*f.t[0][1];
		t2[1]=seg2[e][0]*f.t[1][0]+seg2[e][1]*f.t[1][1];
		seg2[e][0]=t2[0]%mod;
		seg2[e][1]=t2[1]%mod;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=0;
		for(int k=0;k<2;k++)for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=(tmp.t[i][j]+f.t[i][k]*seg1[e].t[k][j])%mod;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)seg1[e].t[i][j]=tmp.t[i][j];
		return;
	}
	if(flag[e]){
		flag[e*2]=flag[e*2+1]=true;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=0;
		for(int k=0;k<2;k++)for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=(tmp.t[i][j]+seg1[e].t[i][k]*seg1[e*2].t[k][j])%mod;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)seg1[e*2].t[i][j]=tmp.t[i][j];
		t2[0]=seg2[e*2][0]*seg1[e].t[0][0]+seg2[e*2][1]*seg1[e].t[0][1];
		t2[1]=seg2[e*2][0]*seg1[e].t[1][0]+seg2[e*2][1]*seg1[e].t[1][1];
		seg2[e*2][0]=t2[0]%mod;
		seg2[e*2][1]=t2[1]%mod;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=0;
		for(int k=0;k<2;k++)for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=(tmp.t[i][j]+seg1[e].t[i][k]*seg1[e*2+1].t[k][j])%mod;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)seg1[e*2+1].t[i][j]=tmp.t[i][j];
		t2[0]=seg2[e*2+1][0]*seg1[e].t[0][0]+seg2[e*2+1][1]*seg1[e].t[0][1];
		t2[1]=seg2[e*2+1][0]*seg1[e].t[1][0]+seg2[e*2+1][1]*seg1[e].t[1][1];
		seg2[e*2+1][0]=t2[0]%mod;
		seg2[e*2+1][1]=t2[1]%mod;
		flag[e]=false;
		seg1[e]=I;
	}
	add(a,(a+b)/2,c,d,e*2,f);
	add((a+b)/2+1,b,c,d,e*2+1,f);
	seg2[e][0]=(seg2[e*2][0]+seg2[e*2+1][0])%mod;
	seg2[e][1]=(seg2[e*2][1]+seg2[e*2+1][1])%mod;
	
}
long long calc(int a,int b,int c,int d,int e){
	if(d<a||b<c)return 0;
	if(c<=a&&b<=d){
	//	return (seg2[e][0]*seg1[e].t[0][0]+seg2[e][1]*seg1[e].t[0][1])%mod;
		return seg2[e][0];
	}
	if(flag[e]){
		flag[e*2]=flag[e*2+1]=true;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=0;
		for(int k=0;k<2;k++)for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=(tmp.t[i][j]+seg1[e].t[i][k]*seg1[e*2].t[k][j])%mod;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)seg1[e*2].t[i][j]=tmp.t[i][j];
		t2[0]=seg2[e*2][0]*seg1[e].t[0][0]+seg2[e*2][1]*seg1[e].t[0][1];
		t2[1]=seg2[e*2][0]*seg1[e].t[1][0]+seg2[e*2][1]*seg1[e].t[1][1];
		seg2[e*2][0]=t2[0]%mod;
		seg2[e*2][1]=t2[1]%mod;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=0;
		for(int k=0;k<2;k++)for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=(tmp.t[i][j]+seg1[e].t[i][k]*seg1[e*2+1].t[k][j])%mod;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)seg1[e*2+1].t[i][j]=tmp.t[i][j];
		t2[0]=seg2[e*2+1][0]*seg1[e].t[0][0]+seg2[e*2+1][1]*seg1[e].t[0][1];
		t2[1]=seg2[e*2+1][0]*seg1[e].t[1][0]+seg2[e*2+1][1]*seg1[e].t[1][1];
		seg2[e*2+1][0]=t2[0]%mod;
		seg2[e*2+1][1]=t2[1]%mod;
		flag[e]=false;
		seg1[e]=I;
	}
	long long ret=(calc(a,(a+b)/2,c,d,e*2)+calc((a+b)/2+1,b,c,d,e*2+1))%mod;

	seg2[e][0]=(seg2[e*2][0]+seg2[e*2+1][0])%mod;
	seg2[e][1]=(seg2[e*2][1]+seg2[e*2+1][1])%mod;
	return ret;
}
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		scanf("%d",p+i);
	}
	for(int i=0;i<a;i++){
		mat tmp=F(p[i]-1);
		seg2[i+131072][0]=tmp.t[0][0];
		seg2[i+131072][1]=tmp.t[1][0];

	}
	for(int i=131071;i>=0;i--){
		seg2[i][0]=(seg2[i*2][0]+seg2[i*2+1][0])%mod;
		seg2[i][1]=(seg2[i*2][1]+seg2[i*2+1][1])%mod;
	}
	for(int i=0;i<262144;i++){
		for(int j=0;j<2;j++)for(int k=0;k<2;k++)seg1[i].t[j][k]=(j==k);
	}
	I.t[0][0]=I.t[1][1]=1;
	while(b--){
		int v;scanf("%d",&v);
		if(v==1){
			int x,y,z;scanf("%d%d%d",&x,&y,&z);x--;y--;
			add(0,131071,x,y,1,F(z));
		}else{
			int x,y;scanf("%d%d",&x,&y);x--;y--;
			printf("%I64d\n",calc(0,131071,x,y,1));
		}
	}
}

D:
重心を求めてから対称性をチェックしつつ非対称な場所を答えに加えるみたいなことをしたけどWAなので、嘘解法なのだろうか。確かにAC人数は少ないけども。

UPD: 解法は合っていた。木の同型性判定をするときは普通のローリングハッシュだと衝突が狙って簡単に起こせるらしく、頂点に変な係数をかけてやったりしないといけないらしい。そのうえジャッジデータには mod 2^k ローリングハッシュを落とすケースもちゃんと存在していた。
今回解いた中で唯一解きがいがあった。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
typedef unsigned long long wolf;
vector<int>g[110000];
wolf key[110000];
int st[110000];
int ra[110000];
wolf ran[]={114514,1919810,364364,4545334};
int n;
const long long M=1000000009;
int dfs(int a,int b){
	int rem=n-1;
	for(int i=0;i<g[a].size();i++){
		if(g[a][i]==b)continue;
		int tmp=dfs(g[a][i],a);
		ra[a]=max(ra[a],tmp);
		rem-=tmp;
		st[a]+=tmp;
	}
	ra[a]=max(ra[a],rem);
	st[a]++;
	return st[a];
}
vector<int>gp;
wolf calc(int a,int b){
	vector<wolf> ch;
	for(int i=0;i<g[a].size();i++){
		if(g[a][i]==b)continue;
		ch.push_back(calc(g[a][i],a));
	}
	std::sort(ch.begin(),ch.end());
	wolf ret=ch.size()+1;
	for(int i=0;i<ch.size();i++){
		ret=(ret*mod+ch[i]*ran[i])%M;
	}
	key[a]=ret;
	return ret;
}
int ans;
void cnt(int a,int b){
	if(g[a].size()<4){
		ans++;
	}
	vector<pair<wolf,int> > v;
	for(int i=0;i<g[a].size();i++){
		if(g[a][i]==b)continue;
		v.push_back(make_pair(key[g[a][i]],g[a][i]));
	}
	std::sort(v.begin(),v.end());
	for(int i=0;i<v.size();i++){
		if(i==0||v[i].first!=v[i-1].first){
			cnt(v[i].second,a);
		}
	}
}
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a-1;i++){
		int p,q;scanf("%d%d",&p,&q);p--;q--;
		g[p].push_back(q);g[q].push_back(p);
	}
	n=a;
	dfs(0,-1);
	int mv=999999999;
	//for(int i=0;i<a;i++)printf("%d\n",ra[i]);
	for(int i=0;i<a;i++)mv=min(mv,ra[i]);
	for(int i=0;i<a;i++)if(ra[i]==mv)gp.push_back(i);
	
	if(gp.size()>2){
		printf("yabai\n");while(1);
	}else if(gp.size()==2){
		calc(gp[0],gp[1]);
		calc(gp[1],gp[0]);
		cnt(gp[0],gp[1]);
		if(key[gp[0]]!=key[gp[1]])cnt(gp[1],gp[0]);
	}else{
		calc(gp[0],-1);
		cnt(gp[0],-1);
	}
	printf("%d\n",ans);
}

*1:多分出題ミスで消えたんだと思う。跡形もなく消え去っていた。