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

Good Bye 2016

Codeforces

思えば3年前、Good Bye 2013では問題もろくに解けずHackすることだけしてレートを減らしていました。
tozangezan.hatenablog.com

3年後、Codeforcesをやる気になったためついに戻ってきました。

A B C D E F G H Place
00:24 00:10 00:06 00:21 01:09 - - - 44th

Rating: 25102581 (+71)
残念でした。IGMにはなれませんでした。

A:
これはどうでもいいです。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int b[32];
int vis[410][410];
bool f[410][410][30][8];
int dx[]={1,1,0,-1,-1,-1,0,1};
int dy[]={0,1,1,1,0,-1,-1,-1};
int D=200;
int main(){
	int a,b;scanf("%d%d",&a,&b);
	int t=(240-b)/5;
	for(int i=a;i>=0;i--){
		if(i*(i+1)/2<=t){
			printf("%d\n",i);
			return 0;
		}
	}
}

B:
問題文を読めればどうでもいいです。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
char in[510];
int main(){
	int a;scanf("%d",&a);
	int at=0;
	while(a--){
		int b;scanf("%d%s",&b,in);
		if(in[0]=='S'){
			if(at+b>20000){
				printf("NO\n");return 0;
			}
			at+=b;
		}else if(in[0]=='N'){
			if(at-b<0){
				printf("NO\n");return 0;
			}
			at-=b;
		}else{
			if(at==0||at==20000){
				printf("NO\n");return 0;
			}
		}
	}
	if(at==0)printf("YES\n");else printf("NO\n");
}

C:
直感的に思ったことを書けば通ります。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int p[210000];
int q[210000];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d%d",p+i,q+i);
	}
	int tt=0;
	for(int i=0;i<a;i++)if(q[i]==2)tt++;
	if(!tt){
		printf("Infinity\n");return 0;
	}
	int L=-999999999;
	int R=999999999;
	for(int i=0;i<a;i++){
		if(q[i]==1){
			L=max(L,1900);
		}else{
			R=min(R,1899);
		}
		L+=p[i];
		R+=p[i];
	//	printf("%d %d\n",L,R);
	}
	if(L>R){
		printf("Impossible\n");return 0;
	}
	printf("%d\n",R);
}

D:
適当にBFSしてください。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int b[32];
int vis[410][410];
bool f[410][410][30][8];
int dx[]={1,1,0,-1,-1,-1,0,1};
int dy[]={0,1,1,1,0,-1,-1,-1};
int D=200;
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d",b+i);
	}
	b[0]--;
	queue<pair<pair<int,int>,pair<int,int> > > Q;
	Q.push(make_pair(make_pair(D,D),make_pair(0,0)));
	f[D][D][0][0]=1;
	while(Q.size()){
		int row=Q.front().first.first;
		int col=Q.front().first.second;
		int ph=Q.front().second.first;
		int dir=Q.front().second.second;Q.pop();
		vis[row][col]=1;
		for(int i=0;i<b[ph];i++){
			row+=dx[dir];
			col+=dy[dir];
			vis[row][col]=1;
		}
		if(ph==a-1)continue;

		if(!f[row][col][ph+1][(dir+1)%8]){
			f[row][col][ph+1][(dir+1)%8]=true;
			Q.push(make_pair(make_pair(row,col),make_pair(ph+1,(dir+1)%8)));
		}
		if(!f[row][col][ph+1][(dir+7)%8]){

			f[row][col][ph+1][(dir+7)%8]=true;
			Q.push(make_pair(make_pair(row,col),make_pair(ph+1,(dir+7)%8)));
		}
	}
	int ret=0;
	for(int i=0;i<410;i++)for(int j=0;j<410;j++)ret+=vis[i][j];
		printf("%d\n",ret);
}

E:
AtCoderでも見た、SegtreeにDPの状態i→jのコストをもっておくやつです。もしかしたらこれをライブラリにしておくと強いかも。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
char in[210000];
struct wolf{
	int t[5][5];
	wolf(){for(int i=0;i<5;i++)for(int j=0;j<5;j++)t[i][j]=-1;}
};
wolf segtree[524288];
wolf zero;
wolf dame;
wolf query(int a,int b,int c,int d,int e){
	if(d<=a||b<=c)return zero;
	if(c<=a&&b<=d){
		//printf("%d %d %d %d %d\n",a,b,c,d,e);

		return segtree[e];
	}
	wolf L=query(a,(a+b)/2,c,d,e*2);
	wolf R=query((a+b)/2,b,c,d,e*2+1);
	//for(int i=0;i<5;i++){
//		for(int j=0;j<5;j++)printf("%d ",R.t[i][j]);printf("\n");
//	}
	wolf ret;
	for(int i=0;i<5;i++)for(int j=i;j<5;j++){
		for(int k=i;k<=j;k++){
			//printf("%d %d %d\n",L.t[i][k],R.t[k][j],ret.t[i][j]);
			if(~L.t[i][k]&&~R.t[k][j]&&(ret.t[i][j]==-1||ret.t[i][j]>L.t[i][k]+R.t[k][j])){

				ret.t[i][j]=L.t[i][k]+R.t[k][j];
			}
		}
	}
	return ret;
}
int main(){
	int a,b;scanf("%d%d",&a,&b);
	scanf("%s",in);
	for(int i=0;i<a;i++){
		for(int j=0;j<5;j++)segtree[i+262144].t[j][j]=0;
		if(in[i]=='2'){
			segtree[i+262144].t[0][0]=1;
			segtree[i+262144].t[0][1]=0;
		}else if(in[i]=='0'){
			segtree[i+262144].t[1][1]=1;
			segtree[i+262144].t[1][2]=0;
		}else if(in[i]=='1'){
			segtree[i+262144].t[2][2]=1;
			segtree[i+262144].t[2][3]=0;
		}else if(in[i]=='6'){
			segtree[i+262144].t[3][3]=1;
			segtree[i+262144].t[4][4]=1;
		}else if(in[i]=='7'){
			segtree[i+262144].t[3][3]=1;
			segtree[i+262144].t[3][4]=0;
		}
		
	}
	for(int i=a;i<262144;i++)for(int j=0;j<5;j++)segtree[i+262144].t[j][j]=0;
	for(int i=262143;i>0;i--){
		for(int j=0;j<5;j++)for(int k=j;k<5;k++){
			for(int l=j;l<=k;l++){
				if(segtree[i*2].t[j][l]==-1||segtree[i*2+1].t[l][k]==-1)continue;
				if(~segtree[i].t[j][k])segtree[i].t[j][k]=min(segtree[i].t[j][k],segtree[i*2].t[j][l]+segtree[i*2+1].t[l][k]);
				else segtree[i].t[j][k]=segtree[i*2].t[j][l]+segtree[i*2+1].t[l][k];
			}
		}
	}
	for(int i=0;i<5;i++)zero.t[i][i]=0;
	for(int i=0;i<5;i++)for(int j=0;j<5;j++)dame.t[i][j]=-1;
	while(b--){
		int p,q;scanf("%d%d",&p,&q);p--;
		wolf res=query(0,262144,p,q,1);

		printf("%d\n",res.t[0][4]);
	}
}

F:
解法は単純なのですが、コードに落とすのが大変です。ICPCの参加権がある人は練習にやってみては?