JOI2015予選の問題を解いてみた

こんにちは,chigichanです.

実際にコンテストの行われていた時間に参加したわけではないですが,解いてみました.
2時間半くらいであきらめました.

結果は520点でした.

今年は難化すると思ってたらめっちゃ易化してたのでびっくりです.
特に3問目がもはややるだけとなっていたので...

template

#include <bits/stdc++.h>
using namespace std;
const int dx[]={1,0,-1,0,1,-1,-1,1};
const int dy[]={0,1,0,-1,1,1,-1,-1};
const int INF = 1<<30;
const int EPS = 1e-8;
#define PB push_back
#define mk make_pair
#define fi first
#define se second
#define ll long long
#define reps(i,j,k) for(int i = (j); i < (k); i++)
#define rep(i,j) reps(i,0,j)
#define MOD 1000000007
typedef pair<int,int> Pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

1問目

minとるだけ

int main(){
	int A,B,C,D,P;
	cin >> A >> B >> C >> D >> P;
	int X = P*A;
	int Y = B;
	if(P > C){
		int Z = P-C;
		Y += Z*D;
	}
	cout << min(X,Y) << "\n";		
	return 0;
}

2問目

問題文の通りにシミュレート

int target[128];
int score[128];
int main(){
	int N;
	int M;
	cin >> N >> M;
	rep(i,M){
		cin >> target[i];
	}
	rep(i,M){
		int miss = 0;
		rep(j,N){
			int tmp;
			cin >> tmp;
			if(tmp == target[i]){
				score[j]++;
			}
			else miss++;
		}
		score[target[i]-1]+=miss;
	}
	rep(i,N){
		cout << score[i] << "\n";
	}
	return 0;
}

3問目

言われた通りに書くだけ.
自分の直前の'c'の位置を持つと引くだけになる.

string stage[128];
int main(){
	int H,W;
	cin >> H >> W;
	rep(i,H){
		int bef = -1;
		cin >> stage[i];
		rep(j,W){
			if(stage[i][j] == 'c'){
				printf("0");
				bef = j;
			}
			else{
				if(bef == -1){
					printf("-1");
				}
				else{
					printf("%d",j-bef);
				}
			}
			printf("%c",j == W-1?'\n':' ');
		}
	}
	return 0;
}

4問目

i番目の町にj日目に来た時の疲労の最小値みたいな感じでdp
再帰でかくとチョー楽

int N,M;
int distnce[1024];
int weather[1024];
int memo[1024][1024];
int solve(int index,int day){
	if(day == M){
		if(index == N)return 0;
		return INF;
	}
	if(memo[index][day])return memo[index][day];
	int ans = INF;
	ans = min(solve(index,day+1),solve(index+1,day+1)+weather[day]*distnce[index]);
	return memo[index][day] = ans;
}
int main(){
	cin >> N >> M;
	rep(i,N){
		cin >> distnce[i];
	}
	rep(i,M){
		cin >> weather[i];
	}
	printf("%d\n",solve(0,0));
	return 0;
}

5問目

はじめ,パッとした解法浮かばなかったので,シミュレートしたら1個だけ通った.
そのあと考えたら(x,y)にくる波が来た回数をメモっておいて,それが城の耐久度分きたらそこに,
波を生成すればいい.
BFSの要素にx,yに加えて,何回目の波かを持っておけば勝ち.

char stage[1024][1024];
class data{
public:
	int y;
	int x;
	int cnt;
	data(){}
	data(int _y,int _x,int _cnt){
		y = _y;
		x = _x;
		cnt = _cnt;
	}
};
int memo[1024][1024];
int main(){
	int H,W;
	cin >> H >> W;
	queue < data > Q; 
	rep(i,H){
		cin >> stage[i];
		rep(j,W){
			if(stage[i][j] == '.'){
				Q.push(data(i,j,0));
			}
		}
	}
	int ans = 0;
	while(!Q.empty()){
		data d = Q.front();Q.pop();
		rep(i,8){
			int ny = d.y + dy[i];
			int nx = d.x + dx[i];
			if(ny < 0 || ny > H-1 || nx < 0 || nx > W-1)continue;
			memo[ny][nx]++;
			if(memo[ny][nx]==stage[ny][nx]-'0'){
				Q.push(data(ny,nx,d.cnt+1));
				ans = max(ans,d.cnt+1);
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

6問目

わからん.
全探索だと3^Nが生えてくる.
1部分点取れるコード.

半分全列挙でやるといいらしいが今日はもう眠いのでまた今度.

typedef pair<ll,ll> Pll;
int N;
ll D;

vector < Pll > data;
ll solve(int dep,Pll Anna,Pll Bruno){
	if(dep == N){
		if(abs(Anna.fi - Bruno.fi) <= D)return Bruno.se-Anna.se;
		return -INF;
	}
	ll ans = -INF;
	
	ans = max(ans,solve(dep+1,mk(Anna.fi+data[dep].fi,Anna.se+data[dep].se),Bruno));
	ans = max(ans,solve(dep+1,Anna,mk(Bruno.fi+data[dep].fi,Bruno.se+data[dep].se)));
	ans = max(ans,solve(dep+1,Anna,Bruno));
	return ans;
}
int main(){
	cin >> N >> D;
	rep(i,N){
		ll x,y;
		cin >> x >> y;
		data.PB(mk(x,y));
	}
	printf("%lld\n",solve(0,mk(0,0),mk(0,0)));	
	return 0;
}

後輩は4人くらい通りそうな勢いらしい.
個人的にボーダーは380かなと言う感じ.

それでは.