tozangezan's diary

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

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

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

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を勉強する(これも虚無)か、虚無を実装するか。木分解でもうまくいきそうに見えるけどどうなんだこれ。