読者です 読者をやめる 読者になる 読者になる

最大独立集合 速め

Tips

696Mediumで書いたもの。38頂点を1000回実行して200ms弱と相当速い。
s[i][j]: 隣接行列
S[i]: 隣接行列を詰め込んだもの
v[i]: 頂点の利用状況
val: 答え
uk: v[i]=0のiを詰め込んだもの
n: 頂点数

int s[40][40];
long long S[40];
int v[40];
int val;
int n;
long long uk=0;
void calc(){
	int nm=0;
	for(int i=0;i<n;i++)if(v[i]==1)nm++;
	val=max(val,nm);
	for(int i=0;i<n;i++){
		if(v[i]==0&&__builtin_popcountll(uk&S[i])<2){
			v[i]=1;
			uk-=1LL<<i;
			long long ch=0;
			for(int j=0;j<n;j++)if(v[j]==0&&s[i][j]){v[j]=2;ch+=1LL<<j;uk-=1LL<<j;}
			calc();
			v[i]=0;
			uk+=1LL<<i;
			for(int j=0;j<n;j++)if(ch&(1LL<<j)){v[j]=0;uk+=1LL<<j;}
			return;
		}
	}
	int dm=1;
	int at=-1;
	for(int i=0;i<n;i++){
		if(v[i]==0&&__builtin_popcountll(uk&S[i])>=dm){
			dm=__builtin_popcountll(uk&S[i]);
			at=i;
		}
	}
	if(at==-1)return;
	v[at]=2;
	uk-=1LL<<at;
	calc();
	v[at]=0;
	uk+=1LL<<at;
	
	v[at]=1;
	uk-=1LL<<at;
	long long ch=0;
	for(int j=0;j<n;j++){
		if(v[j]==0&&s[at][j]){
			v[j]=2;
			uk-=1LL<<j;
			ch+=(1LL<<j);
		}
	}
	calc();
	for(int j=0;j<n;j++){
		if(ch&1LL<<j){v[j]=0;uk+=1LL<<j;}
	}
	v[at]=0;uk+=1LL<<at;
}

698F: Coprime Permutation

Codeforces

素因数→素因数の写像が何通りあるかと、それぞれの素因数内で数の並べ方が何通りあるか掛け算する。
前者は、同じ回数出現する素因数が自由に入れ替えられるので、それぞれの素因数に対して、indexにその素因数をもつ場所のgcdを求めて、対応をつけると自由度がわかので階乗をかける。
後者は、(素因数の集合)ごとに独立で、これも前計算してから同様に自由度を求めて階乗をかける。

でも証明はできていない。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int b[1100000];
int pr[1100000];
int st[1100000];
int to[1100000];
int val[1100000];
int wk[1100000];
int tk[1100000];
long long fact[1100000];
long long gcd(long long a,long long b){
	while(a){
		b%=a;swap(a,b);
	}
	return b;
}
int pl[110000];
int dec[1100000];
int used[1100000];
vector<int> pp[1100000];
int main(){
	int a;scanf("%d",&a);
	fact[0]=1;
	for(int i=1;i<1100000;i++)fact[i]=fact[i-1]*i%mod;
	for(int i=0;i<a;i++){
		scanf("%d",b+i);
	}
	pr[0]=pr[1]=-1;
	for(int i=2;i<1100000;i++){
		if(pr[i]==-1)continue;
		pr[i]=1;
		for(int j=i+i;j<1100000;j+=i)pr[j]=-1;
	}
	st[1]++;
	for(int i=2;i<=a;i++){
		if(pr[i]==1){
			st[a/i]++;
			for(int j=i;j<=a;j+=i)pp[j].push_back(i);
		}
	}
	int ind=0;
	for(int i=2;i<1100000;i++){
		if(pr[i]==1)pl[ind++]=i;
	}
	long long ret=1;
	if(pr[b[0]]==1||b[0]==1){
		used[b[0]]=1;
		dec[1]++;
	}
	for(int i=1;i<=a;i++){
		if(pr[i]==1){
			int now=0;
			for(int j=i;j<=a;j+=i){
				if(!b[j-1])continue;
				now=gcd(now,b[j-1]);
			}
			if(now!=0){
				bool ok=false;
				int ss=-1;
				for(int j=0;j<pp[now].size();j++){
					if(a/pp[now][j]==a/i){
						ss=pp[now][j];
						ok=true;break;
					}
				}
				if(!ok&&a/i==1&&now==1){
					ss=now;
					ok=true;
				}
			//	printf("%d: %d %d\n",i,now,ss);
				if(used[ss]||!ok){

					printf("0\n");return 0;
				}
				used[ss]=1;
				dec[a/i]++;
			}
		}
	}
	for(int i=1;i<=a;i++)ret=ret*fact[st[i]-dec[i]]%mod;
	for(int i=1;i<=a;i++)val[i]=1;
	for(int i=2;i<=a;i++){
		if(pr[i]==1){
			for(int j=i;j<=a;j+=i)val[j]*=i;
		}
	}
	for(int i=1;i<=a;i++)wk[val[i]]++;
	for(int i=0;i<a;i++){
		if(b[i])tk[val[b[i]]]++;
	}
	for(int i=1;i<=a;i++)ret=ret*fact[wk[i]-tk[i]]%mod;
	printf("%I64d\n",ret);
}

Codeforces Round #348 (VK Cup 2016 Round 2, Div. 1 Edition)

Codeforces

何だこのセットは......。難問が誰にも存在しないセットだと、簡単が速いから勝ててしまう。

A B C D E F Place
00:13 00:06 00:34 (+1) 00:48 - - 4th

A:
逆からやるだけ。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int p[11000][4];
int mat[110][110];
int main(){
	int a,b,c;scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<c;i++){
		scanf("%d%d",&p[i][0],&p[i][1]);
		p[i][1]--;
		if(p[i][0]==3){
			scanf("%d%d",&p[i][2],&p[i][3]);
			p[i][2]--;
		}
	}
	for(int i=c-1;i>=0;i--){
		if(p[i][0]==3){
			mat[p[i][1]][p[i][2]]=p[i][3];
		}else if(p[i][0]==2){
			int tmp=mat[a-1][p[i][1]];
			for(int j=a-1;j>0;j--){
				mat[j][p[i][1]]=mat[j-1][p[i][1]];
			}
			mat[0][p[i][1]]=tmp;
		}else{
			int tmp=mat[p[i][1]][b-1];
			for(int j=b-1;j>0;j--){
				mat[p[i][1]][j]=mat[p[i][1]][j-1];
			}
			mat[p[i][1]][0]=tmp;
		}
	}
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			if(j)printf(" ");
			printf("%d",mat[i][j]);
		}
		printf("\n");
	}
}

B:
偶奇ごとに持っておけば、偶数奇数それぞれの中では平行移動してるだけ。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int ret[1100000];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	int p1=0;
	int p2=1;
	while(b--){
		int c;scanf("%d",&c);
		if(c==1){
			int d;scanf("%d",&d);
			p1+=d;
			p2+=d;
			if(p1<0)p1+=a;
			if(p2<0)p2+=a;
			if(p1>=a)p1-=a;
			if(p2>=a)p2-=a;
			
		}else{
			p1^=1;
			p2^=1;
		}
	}
	for(int i=0;i<a/2;i++){
		ret[(p1+i*2)%a]=i*2+1;
		ret[(p2+i*2)%a]=i*2+2;
	}
	for(int i=0;i<a;i++){
		if(i)printf(" ");
		printf("%d",ret[i]);
	}
	printf("\n");
}

C:
手元で二次方程式を解く・sqrtの中身を負にしないように

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
double A[110000];
double B[110000];

double x[110000];
double y[110000];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%lf",A+i);
	for(int i=0;i<a;i++)scanf("%lf",B+i);
	double p1=0;
	double p2=0;
	for(int i=0;i<a;i++)p2+=B[i];
	for(int i=0;i<a-1;i++){
		p1+=A[i];
		p2-=B[i];
		y[i]=0.5*((p1-p2+1)+sqrt(max(0.0,(p1-p2+1)*(p1-p2+1)-4.0*p1)));
		x[i]=0.5*((p1-p2+1)-sqrt(max(0.0,(p1-p2+1)*(p1-p2+1)-4.0*p1)));
	}
	x[a-1]=y[a-1]=1;
	for(int i=a-1;i>0;i--){
		x[i]-=x[i-1];
		y[i]-=y[i-1];
	}
	for(int i=0;i<a;i++){
		if(i)printf(" ");
		printf("%.12f",x[i]);
	}
	printf("\n");
	for(int i=0;i<a;i++){
		if(i)printf(" ");
		printf("%.12f",y[i]);
	}
	printf("\n");
	
}

D:
追加する数ごとに独立で、内部でも座標圧縮してBITするだけ...。残り2問と比べてあまりにも簡単すぎる。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int x[110000];
int b[110000];
int t[110000];
int z[110000];
vector<int>q[110000];
int bit[110000];
int sz;
int sum(int a,int b){
	if(a)return sum(0,b)-sum(0,a-1);
	int ret=0;
	for(;b>=0;b=(b&(b+1))-1)ret+=bit[b];
	return ret;
}
void add(int a,int b){
	for(;a<sz;a|=a+1)bit[a]+=b;
}
int z2[110000];
int ans[110000];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d%d%d",b+i,t+i,x+i);
		z[i]=x[i];
	}
	std::sort(z,z+a);
	for(int i=0;i<a;i++){
		int at=lower_bound(z,z+a,x[i])-z;
		q[at].push_back(i);
	}
	for(int i=0;i<a;i++){
		if(q[i].size()){
			sz=q[i].size();
			for(int j=0;j<q[i].size();j++){
				z2[j]=t[q[i][j]];
			}
			std::sort(z2,z2+sz);
			for(int j=0;j<q[i].size();j++){
				int ind=lower_bound(z2,z2+sz,t[q[i][j]])-z2;
				if(b[q[i][j]]==1){
					add(ind,1);
				}else if(b[q[i][j]]==2){
					add(ind,-1);
				}else{
					ans[q[i][j]]=sum(0,ind);
				}
			}
			for(int j=0;j<sz;j++)bit[j]=0;
		}
	}
	for(int i=0;i<a;i++){
		if(b[i]!=3)continue;
		printf("%d\n",ans[i]);
	}
}

F:
虚無。
Black box linear algebraを勉強する(これも虚無)か、虚無を実装するか。木分解でもうまくいきそうに見えるけどどうなんだこれ。

第3回 Dwangoからの挑戦状 Finals

Contest

えええ....。せっかくの優勝チャンスを逃した。

A B C D Place
118:47 70:40 (+2) 47:52 (+2) - 5th

A:
ずっと前から見てて解けないと思ってトイレにいったら後ろからやるだけだった。こういうのが遅いのはダメでしょ

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
char in[100];
int dp[60][60][60][2];
int v[60][60][60];
void solve(int a,int b,int c){
	if(v[a][b][c])return ;
	v[a][b][c]=1;
	// +
 
	dp[a][b][c][0]=-mod;
	dp[a][b][c][1]=mod;
	int rem=c;
	if(in[b]!='+')rem--;
	for(int i=a;i<b;i++){
		for(int j=0;j<=rem;j++){
			solve(a,i,j);
			solve(i+1,b-1,rem-j);
			if(dp[a][i][j][0]>-mod&&dp[i+1][b-1][rem-j][0]>-mod){
				dp[a][b][c][0]=max(dp[a][i][j][0]+dp[i+1][b-1][rem-j][0],dp[a][b][c][0]);
				dp[a][b][c][1]=min(dp[a][i][j][1]+dp[i+1][b-1][rem-j][1],dp[a][b][c][1]);	
			}
		}
	}
	// -
	rem=c;
	if(in[b]!='-')rem--;
	for(int i=a;i<b;i++){
		for(int j=0;j<=rem;j++){
			solve(a,i,j);
			solve(i+1,b-1,rem-j);
			if(dp[a][i][j][0]>-mod&&dp[i+1][b-1][rem-j][0]>-mod){
				dp[a][b][c][0]=max(dp[a][i][j][0]-dp[i+1][b-1][rem-j][1],dp[a][b][c][0]);
				dp[a][b][c][1]=min(dp[a][i][j][1]-dp[i+1][b-1][rem-j][0],dp[a][b][c][1]);	
			}
		}
	}
	if(a==b){
		if(c){
			dp[a][b][c][0]=max(dp[a][b][c][0],9);
			dp[a][b][c][1]=min(dp[a][b][c][1],0);
			
		}
		if('0'<=in[a]&&in[a]<='9'){
			dp[a][b][c][0]=max(dp[a][b][c][0],in[a]-'0');
			dp[a][b][c][1]=min(dp[a][b][c][1],in[a]-'0');
		}
	}
}
int main(){
	int a;scanf("%d%s",&a,in);
	int n=strlen(in);
	solve(0,n-1,a);
	if(dp[0][n-1][a][0]==-mod){
		printf("NG\n");return 0;
	}else printf("OK\n%d\n",dp[0][n-1][a][0]);
}

B:
はじめてのMo。速くできるのはわかるけども、速くしなくても定数倍で1/2くらいの割合の人が通るみたいなのは、経験のあるwriterがやるはずないですよね。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int si[11000];
 
int v[110000];
vector<pair<int,int> >ss[110000];
long long ret=1;
long long inv[2200000];
long long ans[110000];
int SQ=300;
vector<pair<pair<int,int>,int> > ev[350]; // rm, lm, id
int main(){
 
	int a,b;scanf("%d%d",&a,&b);
	inv[1]=1;
	for(int i=2;i<2200000;i++){
		inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	}
	for(int i=0;i<a;i++){
		int p;scanf("%d",&p);
		for(int j=2;j*j<=p;j++){
			if(p%j==0){
				int cur=0;
				while(p%j==0){
					p/=j;cur++;
				}
				ss[i].push_back(make_pair(j,cur));
				v[j]=1;
			}
		}
		if(p>1){
			v[p]=1;
			ss[i].push_back(make_pair(p,1));
		}
	}
	int sz=0;
	for(int i=0;i<110000;i++){
		if(v[i])v[i]=sz++;
	}
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);p--;
		ev[p/SQ].push_back(make_pair(make_pair(q,p),i));
	}
	for(int i=0;i<350;i++){
		std::sort(ev[i].begin(),ev[i].end());
	}
	for(int i=0;i<350;i++){
		int l=i*SQ;
		int r=i*SQ;
		for(int j=0;j<sz;j++)si[j]=1;
		ret=1;
		for(int j=0;j<ev[i].size();j++){
			int p=ev[i][j].first.second;
			int q=ev[i][j].first.first;
			int id=ev[i][j].second;
			if(r<q){
				while(r<q){
					for(int k=0;k<ss[r].size();k++){
						int to=ss[r][k].first;
						int am=ss[r][k].second;
						ret=(ret*(si[v[to]]+am)%mod*inv[si[v[to]]])%mod;
						si[v[to]]+=am;
					}
					r++;
				}
			}
			if(l>p){
				while(l>p){
					for(int k=0;k<ss[l-1].size();k++){
						int to=ss[l-1][k].first;
						int am=ss[l-1][k].second;
						ret=(ret*(si[v[to]]+am)%mod*inv[si[v[to]]])%mod;
						si[v[to]]+=am;
					}
					l--;
				}
			}
			if(r>q){
				while(r>q){
					r--;
					for(int k=0;k<ss[r].size();k++){
						int to=ss[r][k].first;
						int am=-ss[r][k].second;
						ret=(ret*(si[v[to]]+am)%mod*inv[si[v[to]]])%mod;
						si[v[to]]+=am;
					}
				}
			}
			if(l<p){
				while(l<p){
					for(int k=0;k<ss[l].size();k++){
						int to=ss[l][k].first;
						int am=-ss[l][k].second;
						ret=(ret*(si[v[to]]+am)%mod*inv[si[v[to]]])%mod;
						si[v[to]]+=am;
					}
					l++;
				}
			}
			ans[id]=ret;
		}
	}
	for(int i=0;i<b;i++)printf("%lld\n",ans[i]);
}

C:
点を含む丸を121回で見つけたら、丸をどのくらい上に動かしても大丈夫か、どのくらい右に動かしても大丈夫かを二分探索で求めて。円の交点のどっちか1つが答え。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
char in[110];
const double EPS = 1e-10;
const double INF = 1e+10;
const double PI = acos(-1);
int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
inline double ABS(double a){return max(a,-a);}
struct Pt {
	double x, y;
	Pt() {}
	Pt(double x, double y) : x(x), y(y) {}
	Pt operator+(const Pt &a) const { return Pt(x + a.x, y + a.y); }
	Pt operator-(const Pt &a) const { return Pt(x - a.x, y - a.y); }
	Pt operator*(const Pt &a) const { return Pt(x * a.x - y * a.y, x * a.y + y * a.x); }
	Pt operator-() const { return Pt(-x, -y); }
	Pt operator*(const double &k) const { return Pt(x * k, y * k); }
	Pt operator/(const double &k) const { return Pt(x / k, y / k); }
	double ABS() const { return sqrt(x * x + y * y); }
	double abs2() const { return x * x + y * y; }
	double arg() const { return atan2(y, x); }
	double dot(const Pt &a) const { return x * a.x + y * a.y; }
	double det(const Pt &a) const { return x * a.y - y * a.x; }
};
double tri(const Pt &a, const Pt &b, const Pt &c) { return (b - a).det(c - a); }
pair<Pt,Pt> pCC(Pt a, double r, Pt b, double s) {
	double d = (b - a).ABS();
	double x = (d * d + r * r - s * s) / (d * 2);
	Pt e = (b - a) / d, w = e * Pt(0, 1) * sqrt(max(r * r - x * x, 0.0));
	return make_pair(a + e * x - w, a + e * x + w);
}
Pt c;
int main(){
	bool ok=false;
	for(int i=0;i<=10;i++){
		if(ok)break;
		for(int j=0;j<=10;j++){
			if(ok)break;
			printf("%d %d\n",i*100000,j*100000);fflush(stdout);
			scanf("%s",in);
			if(in[1]=='o')return 0;
			if(in[1]=='l'){
				ok=true;
				c=Pt(i*100000,j*100000);
			}
		}
	}
	double left=0;
	double right=200000;
	for(int i=0;i<35;i++){
		double M=(left+right)/2;
		printf("%.12f %.12f\n",c.x+M,c.y);
		fflush(stdout);
		scanf("%s",in);
		if(in[1]=='o')return 0;
		if(in[1]=='l')left=M;
		else right=M;
	}
	double X=c.x+left;
	left=0;
	right=200000;
	for(int i=0;i<35;i++){
		double M=(left+right)/2;
		printf("%.12f %.12f\n",c.x,c.y+M);
		fflush(stdout);
		scanf("%s",in);
		if(in[1]=='o')return 0;
		if(in[1]=='l')left=M;
		else right=M;
	}
	double Y=c.y+left;
	pair<Pt,Pt> tt=pCC(Pt(X,c.y),100000,Pt(c.x,Y),100000);
	int t1=tt.first.x-0.5;
	int t2=tt.first.y-0.5;
	for(int i=0;i<2;i++)for(int j=0;j<2;j++){
		printf("%d %d\n",t1+i,t2+j);fflush(stdout);scanf("%s",in);
		if(in[1]=='o')return 0;
	}
	t1=tt.second.x-0.5;
	t2=tt.second.y-0.5;
	for(int i=0;i<2;i++)for(int j=0;j<2;j++){
		printf("%d %d\n",t1+i,t2+j);fflush(stdout);scanf("%s",in);
		if(in[1]=='o')return 0;
	}
}

D:
どうみても遅延更新segtreeであることはわかるしだいたいこういうことがしたいというのはわかるけども、能力が至らず解けなかった。こういう負け方(敗因が練習不足であるのがはっきりしてるケース)が一番ダメ。

Codeforces Round #349 (Div. 1)

Codeforces

いつもと同じ死に方。成長が見られない。相変わらず注意力が灰底辺。

A B C D E Place
00:48 (+1) 00:35 (+4) 01:59 (+1) - - 59th

A:
メモ化再帰するだけ。メモ化し忘れて1TLE。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
char in[11000];
int dp[11000][3];
set<string>S;
char tmp[4];
int n;
int solve(int a,int b){
	if(~dp[a][b])return dp[a][b];
	if(a==n)return dp[a][b]=1;
	int t=0;
	if(a<=n-2){
		if(b!=0||in[a]!=in[a-2]||in[a+1]!=in[a-1]){
			int res=solve(a+2,0);
			if(res){
				t=res;
				tmp[2]=0;tmp[0]=in[a];tmp[1]=in[a+1];string tt=tmp;S.insert(tt);
			}
		}	
	}
	if(a<=n-3){
		if(b!=1||in[a]!=in[a-3]||in[a+1]!=in[a-2]||in[a+2]!=in[a-1]){
			int res=solve(a+3,1);
			if(res){
				t=res;
				tmp[3]=0;tmp[0]=in[a];tmp[1]=in[a+1];tmp[2]=in[a+2];string tt=tmp;S.insert(tt);
			}
		}	
	}
	return dp[a][b]=t;
}
int main(){
	scanf("%s",in);
	n=strlen(in);
	for(int i=0;i<11000;i++)for(int j=0;j<3;j++)
		dp[i][j]=-1;
	for(int i=5;i<=n;i++){
		solve(i,2);
	}
	printf("%d\n",(int)(S.size()));
	for(set<string>::iterator it=S.begin();it!=S.end();it++)printf("%s\n",(*it).c_str());
}

B:
なにも変な要素がないのにひたすらWA。頭が悪すぎる。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
vector<int>g[3100];
int dist[3100][3100];
int L[3100][3];
int R[3100][3];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);p--;q--;
		g[p].push_back(q);
	}
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++)dist[i][j]=-1;
		queue<int>Q;
		Q.push(i);
		dist[i][i]=0;
		while(Q.size()){
			int at=Q.front();Q.pop();
			for(int j=0;j<g[at].size();j++){
				int to=g[at][j];
				if(dist[i][to]==-1){
					dist[i][to]=dist[i][at]+1;
					Q.push(to);
				}
			}
		}
	}
	for(int i=0;i<a;i++){
		L[i][0]=L[i][1]=L[i][2]=-1;
		for(int j=0;j<a;j++){
			if(i==j)continue;
			if(dist[j][i]==-1)continue;
			if(L[i][0]==-1||dist[j][i]>dist[L[i][0]][i]){
				L[i][2]=L[i][1];
				L[i][1]=L[i][0];
				L[i][0]=j;
			}else if(L[i][1]==-1||dist[j][i]>dist[L[i][1]][i]){
				L[i][2]=L[i][1];
				L[i][1]=j;
			}else if(L[i][2]==-1||dist[j][i]>dist[L[i][2]][i]){
				L[i][2]=j;
			}
		}
	}
	for(int i=0;i<a;i++){
		R[i][0]=R[i][1]=R[i][2]=-1;
		for(int j=0;j<a;j++){
			if(i==j)continue;
			if(dist[i][j]==-1)continue;
			if(R[i][0]==-1||dist[i][j]>dist[i][R[i][0]]){
				R[i][2]=R[i][1];
				R[i][1]=R[i][0];
				R[i][0]=j;
			}else if(R[i][1]==-1||dist[i][j]>dist[i][R[i][1]]){
				R[i][2]=R[i][1];
				R[i][1]=j;
			}else if(R[i][2]==-1||dist[i][j]>dist[i][R[i][2]]){
				R[i][2]=j;
			}
		}
	}
	int A,B,C,D;
	int bs=0;
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++){
			for(int k=0;k<3;k++)for(int l=0;l<3;l++){
				if(L[i][k]==-1||R[j][l]==-1||dist[i][j]==-1)continue;
				if(i==j||i==R[j][l]||j==L[i][k]||L[i][k]==R[j][l])continue;
				if(bs<dist[L[i][k]][i]+dist[i][j]+dist[j][R[j][l]]){
					bs=dist[L[i][k]][i]+dist[i][j]+dist[j][R[j][l]];
					A=L[i][k];B=i;C=j;D=R[j][l];
				}
			}
		}
	}
	set<int>S;
	S.insert(A);
	S.insert(B);
	S.insert(C);
	S.insert(D);
	if(S.size()!=4){
		while(1);
	}
	printf("%d %d %d %d\n",A+1,B+1,C+1,D+1);
}

C:
nCkテーブルをsqrt(N)段ごとに作っておいて一行ずつ下がるやつに係数をつけただけ。一箇所-1し忘れ。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
char in[110000];
int n;
int sz=0;
pair<pair<int,int>,int>p[110000];
int ans[110000];
int SQ=300;
long long fact[110000];
long long inv[110000];
long long finv[110000];
long long C(int a,int b){
	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
long long val[110000];
long long sum[110000];
long long p26[110000];
long long p25[110000];
int main(){
	fact[0]=finv[0]=1;
	p26[0]=1;
	p25[0]=1;
	inv[1]=1;
	for(int i=2;i<110000;i++)inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	for(int i=1;i<110000;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
		p26[i]=p26[i-1]*26%mod;
		p25[i]=p25[i-1]*25%mod;
	}
	int a;scanf("%d",&a);
	scanf("%s",in);
	n=strlen(in);
	while(a--){
		int t;scanf("%d",&t);
		if(t==1){
			scanf("%s",in);
			n=strlen(in);
		}else{
			int b;scanf("%d",&b);
			p[sz]=make_pair(make_pair(b,n),sz);
			sz++;
		}
	}
	std::sort(p,p+sz);
	int at=0;
	for(int i=0;i<340;i++){
		long long ks=1;
		for(int j=i*SQ;j>=0;j--){
			val[j]=C(i*SQ,j)*ks;
			ks=ks*25%mod;
		}
		for(int j=0;j<=i*SQ;j++){
			sum[j]=val[j];
			if(j)sum[j]=(sum[j]+sum[j-1])%mod;
		}
		while(at<sz&&p[at].first.first<(i+1)*SQ){

			if(p[at].first.first<p[at].first.second){
				at++;continue;
			}
			long long now=sum[min(i*SQ,p[at].first.second-1)];

			int r=min(i*SQ,p[at].first.second-1);
			for(int j=0;j<p[at].first.first%SQ;j++){
				if(r==p[at].first.second-1){
					now=now*26%mod;
					now=(now+mod-C(i*SQ+j,r)*p25[i*SQ+j-r]%mod)%mod;
				}else{
					now=now*26%mod;
					r++;
				}
			}

			ans[p[at].second]=(p26[p[at].first.first]+mod-now)%mod;
			at++;
		}
	}
	for(int i=0;i<sz;i++)printf("%d\n",ans[i]);
}

Codeforces Round #352 (Div. 1)

Codeforces

心が折れた。
灰コーダー並みの注意力だったのも悪いけど、サンプルも弱いし罠も多すぎだと思う。

A B C D E Place
00:28 (+1) 00:14 (+2) -5 - - 105th

A:
嫌なケースが多すぎる。returnを忘れた。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000010007;
const long long inf=mod*mod;
double x[3];
double y[3];
double X[110000];
double Y[110000];
double dist(double dx,double dy){
	return sqrt(dx*dx+dy*dy);
}
pair<double,int> ta[110000];
pair<double,int> tb[110000];
int main(){
	for(int i=0;i<3;i++){
		scanf("%lf%lf",x+i,y+i);
	}
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%lf%lf",X+i,Y+i);
	}
	if(a==1){
		printf("%.12f\n",min(dist(X[0]-x[0],Y[0]-y[0]),dist(X[0]-x[1],Y[0]-y[1]))+dist(X[0]-x[2],Y[0]-y[2]));
		return 0;
	}
	double ret=0;
	for(int i=0;i<a;i++){
		ret+=dist(X[i]-x[2],Y[i]-y[2])*2;
		ta[i]=make_pair(dist(X[i]-x[0],Y[i]-y[0])-dist(X[i]-x[2],Y[i]-y[2]),i);
		tb[i]=make_pair(dist(X[i]-x[1],Y[i]-y[1])-dist(X[i]-x[2],Y[i]-y[2]),i);
	}
	double ad=99999999999999.9;
	std::sort(ta,ta+a);
	std::sort(tb,tb+a);
	for(int i=0;i<2;i++)for(int j=0;j<2;j++){
		if(ta[i].second==tb[j].second)continue;
		ad=min(ta[i].first+tb[j].first,ad);
	}
	ad=min(ad,min(ta[0].first,tb[0].first));
	printf("%.12f\n",ret+ad);
}

B:
奇数のときは最小1とかいう明確な罠。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000010007;
const long long inf=mod*mod;
int c[510000];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	long long sum=0;
	for(int i=0;i<a;i++){
		scanf("%d",c+i);
		sum+=c[i];
	}
	std::sort(c,c+a);
	int left=0;
	int right=mod;
	while(left+1<right){
		int M=(left+right)/2;
		long long cur=0;
		for(int i=0;i<a;i++){
			if(c[i]<M)cur+=M-c[i];
		}
		if(b<cur){
			right=M;
		}else left=M;
	}
	int q1=left;
	left=0;
	right=mod;
	while(left+1<right){
		int M=(left+right)/2;
		long long cur=0;
		for(int i=0;i<a;i++){
			if(c[i]>M)cur+=c[i]-M;
		}
		if(b<cur){
			left=M;
		}else right=M;
	}
	int q2=right;
	if(q1>q2)q1=q2;
	if(q2-q1==0&&sum%a)q2++;
	printf("%d\n",q2-q1);
}

C:
二重に誤読していた。が解けるものには見えない。

Codeforces Round #359 (Div. 1)

Codeforces

面白いかどうかはさておき、教育された感がある。普段Aからやってると抜かされるのでBからやったら大失敗した。

A B C D E Place
01:01 00:48 - 01:35 - 57th

A:
やるだけ。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int dp[2][1<<7][2];
int p7[24];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	int A=0;
	int B=0;
	int c=a-1;int d=b-1;
	while(c){
		c/=7;
		A++;
	}
	while(d){
		d/=7;
		B++;
	}
	p7[0]=1;
	for(int i=1;i<24;i++)p7[i]=p7[i-1]*7;
	a--;b--;
	if(!A)A++;
	if(!B)B++;
	dp[0][0][0]=1;
	for(int i=0;i<A+B;i++){
		int t=i%2;
		for(int j=0;j<(1<<7);j++)dp[!t][j][0]=dp[!t][j][1]=0;
		for(int j=0;j<(1<<7);j++){
			for(int k=0;k<2;k++){
				if(!dp[t][j][k])continue;
		//		printf("%d %d %d: %d\n",i,j,k,dp[i][j][k]);
				for(int l=0;l<7;l++){
					if(j&(1<<l))continue;
					int tk=k;
					if(i<A){
						if(k==0&&a/p7[A-i-1]%7<l)continue;
						else if(a/p7[A-i-1]%7>l)tk=1;
					}else{
						if(k==0&&b/p7[A+B-i-1]%7<l)continue;
						else if(b/p7[A+B-i-1]%7>l)tk=1;
					}
					if(i==A-1)tk=0;
					dp[!t][j+(1<<l)][tk]+=dp[t][j][k];
				}
			}
		}
	}
	int ret=0;
	for(int i=0;i<(1<<7);i++)for(int j=0;j<2;j++)ret+=dp[(A+B)%2][i][j];
	printf("%d\n",ret);
}

B:
慣れないdsu on treeを練習した。慣れない。あと定数倍がきつすぎ
ポインタに造詣がない人には、dsu on treeのあの書き方はデマ一より有用?

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
vector<int>g[310000];
int sz[310000];
int num;
int L[310000];
int R[310000];
int conv[310000];
int nx[310000];
void dfs(int a){
	sz[a]=1;
	L[a]=num;
	conv[num]=a;
	int mn=0;

	num++;
	for(int i=0;i<g[a].size();i++){
		dfs(g[a][i]);
		sz[a]+=sz[g[a][i]];
		if(mn<sz[g[a][i]]){
			mn=sz[g[a][i]];
			nx[a]=i;
		}
	}
	R[a]=num;
}
int ans[310000];
set<pair<pair<int,int>,int> > S;
set<pair<pair<int,int>,int> > T;
int mx[310000];
void solve(int a,int b){
	int to=-1;

	for(int i=0;i<g[a].size();i++){
		mx[a]=max(mx[a],sz[g[a][i]]);
		if(nx[a]==i){
			to=g[a][i];continue;
		}
		solve(g[a][i],0);

	}
	if(~to)solve(to,1);
	for(int i=0;i<g[a].size();i++){
		if(to==g[a][i])continue;
		solve(g[a][i],1);
	}
	if(!~ans[a]){

	T.insert(make_pair(make_pair(mx[a],sz[a]),a));
	S.insert(make_pair(make_pair(sz[a],mx[a]),a));
	int del=0;
	for(set<pair<pair<int,int>,int> > ::iterator it=S.begin();it!=S.end();it++){
		if((*it).first.first*2<sz[a])del++;
		else break;
	}
	for(int i=0;i<del;i++){
		pair<pair<int,int>,int> tmp=*(S.begin());
		S.erase(tmp);
		swap(tmp.first.first,tmp.first.second);
		T.erase(tmp);
	}
		ans[a]=(*(T.begin())).second;
	}
//	printf("%d: %d %d %d\n",a,T.begin()->first.first,T.begin()->first.second,T.begin()->second);
	if(b==0){
		for(int i=L[a];i<R[a];i++){
			T.erase(make_pair(make_pair(mx[conv[i]],sz[conv[i]]),conv[i]));
			S.erase(make_pair(make_pair(sz[conv[i]],mx[conv[i]]),conv[i]));
		}
	}
}
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a-1;i++){
		int p;scanf("%d",&p);p--;
		g[p].push_back(i+1);
	}
	for(int i=0;i<a;i++)ans[i]=-1;
	dfs(0);
	solve(0,1);
	while(b--){
		int p;scanf("%d",&p);p--;printf("%d\n",ans[p]+1);
	}
}

D:
計算量的には O(n log n+kn)で余裕そうに見えるがO(kn)パートが定数4のついたsetを使うやつで結構重そう、というか実際重い。
Time Limitの設定が総じて雑...?

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000010007;
const long long inf=mod*mod;
int r[110000];
int c[110000];
pair<int,int>p[110000];
pair<int,int>ev[210000];
long long ret[110000];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		scanf("%d%d",r+i,c+i);
		ev[i*2+1]=make_pair(r[i],i+1);
		ev[i*2]=make_pair(r[i]+b,-i-1);
		p[i]=make_pair(c[i],r[i]);
	}
	std::sort(p,p+a);
	std::sort(ev,ev+a*2);
	int last=-mod;
	set<pair<int,pair<int,int> > > S;
	for(int i=0;i<a*2;i++){
	//	printf("%d: %d %d\n",i,ev[i].first,ev[i].second);
		if(i==0||ev[i].first!=ev[i-1].first){
			long long ks=ev[i].first-last;
			int las=-mod;
			int cnt=0;
			for(set<pair<int,pair<int,int> > >::iterator it=S.begin();it!=S.end();it++){
				if(it==S.begin()||((*it).first!=las)){

					if(cnt)ret[cnt]+=((long long)(*it).first-las)*ks;
					las=(*it).first;
				}
				cnt+=(*it).second.first;
			}
			last=ev[i].first;
		}
		if(ev[i].second>0){
			S.insert(make_pair(c[ev[i].second-1],make_pair(1,ev[i].second)));
			S.insert(make_pair(c[ev[i].second-1]+b,make_pair(-1,ev[i].second)));
		}else{
			S.erase(make_pair(c[-ev[i].second-1],make_pair(1,-ev[i].second)));
			S.erase(make_pair(c[-ev[i].second-1]+b,make_pair(-1,-ev[i].second)));
		}
	}
	for(int i=1;i<=a;i++){
		if(i!=1)printf(" ");
		printf("%I64d",ret[i]);
	}
	printf("\n");
}