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

ヘクトのメモ

なんとなくいろいろ書いていくと思います.

Indeedなう 本選A

オープンコンテストに参加して,3完でした.ボーダー突破は難しい.
以下 問題の感想とソースコード

A Table Tennis
貪欲だなと思い,書いたら通る

int n;
int a[110];

int main(void){
	cin >> n;
	rep(i,n) cin >> a[i];
	sort(a,a+n);
	int cmin=2015,cmax=0;
	rep(i,n){
		int cur=a[i]+a[n-1-i];
		cmin=min(cmin,cur);
		cmax=max(cmax,cur);
	}
	cout << cmax-cmin << endl;
	return 0;
}


B Office Ninja
六角座標のダイクストラ.行の偶奇によって,列の遷移先が変わるので注意

int r,c;
string a[110];

int dr[2][6]={
	{-1,-1,0,0,1,1},
	{-1,-1,0,0,1,1}
};
int dc[2][6]={
	{-1,0,-1,1,-1,0},
	{0,1,-1,1,0,1}
};

int dist[110][110];

typedef tuple<int,int,int> state;

int dijkstra(){
	int sr=-1,sc=-1,gr=-1,gc=-1;
	rep(i,r)rep(j,c){
		if(a[i][j]=='s')
			sr=i,sc=j;
		if(a[i][j]=='t')
			gr=i,gc=j;
	}
	rep(i,r)rep(j,c) dist[i][j]=inf;
	dist[sr][sc]=0;
	set<state> s;
	state init(0,sr,sc);
	s.insert(init);
	while(!s.empty()){
		state cur=*(s.begin());
		s.erase(cur);
		int cr,cc,cost;
		tie(cost,cr,cc)=cur;
		if(dist[cr][cc]<cost) continue;
		rep(i,6){
			int nr=cr+dr[cr&1][i];
			int nc=cc+dc[cr&1][i];
			if(nr<0||r<=nr||nc<0||c<=nc) continue;
			int ncost=cost;
			if(isdigit(a[nr][nc]))
				ncost+=(a[nr][nc]-'0');
			if(dist[nr][nc]>ncost){
				dist[nr][nc]=ncost;
				state next(ncost,nr,nc);
				s.insert(next);
			}
		}
	}
	return dist[gr][gc];
}

int main(void){
	cin >> r >> c;
	rep(i,r) cin >> a[i];
	cout << dijkstra() << endl;
	return 0;
}


C Optimal Recommendations
各項目の点数が101通りだから,3次元配列を取る.
memo[a][b][c]=最大年収とすればよい.
そして,memoの情報を伝搬させていくときに,それぞれ小さい方から回す.

int memo[110][110][110];

int main(void){
	int n,m;
	cin >> n >> m;

	rep(i,n){
		int a,b,c,w;
		cin >> a >> b >> c >> w;
		memo[a][b][c]=max(memo[a][b][c],w);
	}
	rep(d,301)rep(i,101)rep(j,101)rep(k,101){
		if(i+j+k==d){
			memo[i+1][j][k]=max(memo[i+1][j][k],memo[i][j][k]);
			memo[i][j+1][k]=max(memo[i][j+1][k],memo[i][j][k]);
			memo[i][j][k+1]=max(memo[i][j][k+1],memo[i][j][k]);
		}
	}
	rep(i,m){
		int x,y,z;
		cin >> x >> y >> z;
		cout << memo[x][y][z] << endl;
	}
	return 0;
}