joi2016予選参戦記 - chigichan24のお気持ち表明

こんにちは．chigichan24です．受験です．

さて，ゴミ年寄りの私はjoi2016の予選に参加してみました．

今年は4問目にDPが来なかったのでウケました．

本当は当日に記事を書こうと思ってたら，

JOI参戦記書こうとしたら4のソースコードのみ紛失していてめんどくなった
— 来世は東京のイケメン男子 (@chigichan24) December 13, 2015

ってなってしまって，もう今日までダラダラと延びてしまいました．

ボーダー予想は420と思っていたのですが，去年の4問目の~~やるだけ~~DPよりは
多少は難しくなってた気もするので，320~360くらいかなと思います．

後輩は怖いのでおそらく2人が全完してるみたいです．
私には追いつけない領域に突入していて，嬉しい一方，自分も頑張らなきゃという気持ちにもなります，

公式がだしている問題のリンクはこっちです．

適当にコードをペタペタ貼る．

1

難易度 : 例年通り
ソート関数とか知らなくても気合のifで通す．

int main(){
    int a[5],b[3];
    rep(i,4){
        cin >> a[i];
    }
    rep(i,2){
        cin >> b[i];
    }

    sort(a,a+4);

    cout << a[1]+a[2]+a[3]+max(b[0],b[1]) << "\n";
    return 0;
}

2

難易度 : 例年通り
与えられたとおりにシミュレート．
剰余算と配列操作を知っておけば楽勝．

int main(){

	int N,M;
	int students[128];
	scanf("%d%d",&N,&M);

	rep(i,N){
		scanf("%d",&students[i]);
	}

	rep(i,M){
		int k = i + 1;
		rep(j,N-1){
			if(students[j] % k > students[j+1] % k){
				swap(students[j],students[j+1]);
			}
		}
	}

	rep(i,N){
		printf("%d\n",students[i]);
	}

	return 0;
}

3

難易度 : 易化
色を変える範囲を全探索．
見るだけ．4重forまでは許される．

int H,W;
//W : 0
//B : 1
//R : 2
int flag[52][52];

int paint(int t1,int t2){
	int cnt = 0;
	rep(i,t1){
		rep(j,W){
			if(flag[i][j] != 0){
				++cnt;
			}
		}
	}

	reps(i,t1,t2){
		rep(j,W){
			if(flag[i][j] != 1){
				++cnt;
			}
		}
	}

	reps(i,t2,H){
		rep(j,W){
			if(flag[i][j] != 2){
				++cnt;
			}
		}
	}

	return cnt;
}

int main(){

	
	scanf("%d%d",&H,&W);
	

	rep(i,H){
		char str[128];
		scanf("%s",str);
		rep(j,W){
			if(str[j] == 'W'){
				flag[i][j] = 0;
			}
			if(str[j] == 'B'){
				flag[i][j] = 1;
			}
			if(str[j] == 'R'){
				flag[i][j] = 2;
			}
		}
	}

	int ans = INF;

	reps(i,1,H){
		reps(j,i+1,H){
			ans = min(ans,paint(i,j));
		}
	}

	printf("%d\n",ans);

	return 0;
}

4

難易度 : 易化(?)
DPじゃないからびっくりのことを考えると，難しいのかも?
けれども，過去の4問目に比べればきっちり考えればできる．
私は，無限時間移動し続けた時の衝突ポイントを探索して，
二分探索で判定するみたいなコードを書きました(紛失)

ll A[100001];
int way[100001];

vector<ll> points;

ll search(int idx,ll T){
	ll l = 0;
	ll r = points.size();
	while(l + 1 != r){
		int med = (l+r)/2;
		if(points[med] > A[idx]){
			r = med;
		}
		else{
			l = med;
		}
	}

	int s;
	ll c;
	if(way[idx] == 1){
		s = l + 1;
		c = 1;
	}
	else if(way[idx] == 2){
		s = l;
		c = -1;
	}
	if(T >= abs(A[idx]-points[s])){
		return points[s];
	}
	return A[idx]+c*T;
}

int main(){
	int N,Q;
	ll T;
	scanf("%d%lld%d",&N,&T,&Q);
	points.PB(-LINF);
	rep(i,N){
		scanf("%lld%d",&A[i],&way[i]);
		if(i > 0 && way[i-1] == 1 && way[i] == 2){
			points.PB(A[i-1]+(A[i]-A[i-1])/2);
		}
	}

	points.PB(LINF);
	rep(i,Q){
		int x;
		scanf("%d",&x);
		--x;
		printf("%lld\n",search(x,T));
	}

	return 0;
}

5

難易度 : 易化
過去問のtaxiとほぼおなじ．
BFSでやばそうな街をどこかにメモしておいて，そのデータを用いてdijkstraする．
最後の街では宿泊しないというあれに気づくのに時間がかかった()

コードが汚いのは許して()

vi ng;

struct edge{
	int to;
	ll cost;
	edge(){}
	edge(int to,ll cost){
		this->to = to;
		this->cost = cost;
	}
	bool operator<(const edge &a)const{
		return cost > a.cost;
	}
};

vector < edge > G[100010];

int main(){
	int N,M,K,S;
	scanf("%d%d%d%d",&N,&M,&K,&S);

	ll P,Q;
	scanf("%lld%lld",&P,&Q);

	rep(i,K){
		int c;
		scanf("%d",&c);
		--c;
		ng.PB(c);
	}

	sort(ng.begin(),ng.end());

	/*rep(i,ng.size()){
		printf("ng : %d\n",ng[i]);
	}*/

	rep(i,M){
		int a,b;
		scanf("%d%d",&a,&b);
		--a;--b;
		G[b].PB(edge(a,P));
		G[a].PB(edge(b,P));
	}


	queue < Pii > Queue;
	int memo[100001] = {0};
	ll dijk[100001];

	rep(i,100001){
		dijk[i] = LINF;
	}

	rep(i,ng.size()){
		Queue.push(Pii(ng[i],S));
	}

	while(!Queue.empty()){
		Pii p = Queue.front();Queue.pop();

		if(memo[p.fr] != 0)continue;
		memo[p.fr] = 1;
		if(binary_search(ng.begin(),ng.end(),p.fr) == true){
			memo[p.fr] = 2;
		}

		if(p.sc == 0)continue;

		rep(i,G[p.fr].size()){
			Queue.push(Pii(G[p.fr][i].to,p.sc-1));
		}

	}

	/*rep(i,N){
		printf("[%d] : %d\n",i,memo[i]);
	}*/

	priority_queue < edge > pq;
	pq.push(edge(0,0));

	while(!pq.empty()){
		edge e = pq.top();pq.pop();

		if(dijk[e.to] != LINF)continue;
		dijk[e.to] = e.cost;

		rep(i,G[e.to].size()){
			if(G[e.to][i].to == N-1){
				pq.push(edge(N-1,e.cost));
			}
			if(memo[G[e.to][i].to] != 0){
				if(memo[G[e.to][i].to] == 2)continue;
				pq.push(edge(G[e.to][i].to,Q + e.cost));
			}
			else pq.push(edge(G[e.to][i].to,P + e.cost));
		}

	}

	printf("%lld\n",dijk[N-1]);


	return 0;
}

6

多分タイルの敷き詰め系bitDPをすれば解けるはず(自分が解けるとは言っていない)．

まとめ

アホすぎて辛い．
この記事書いているのも実質手書きの製図をやりたくないからという理由なのでくそ．
りゅーくんの予言tweetはすごいと思った．

4番DP廃止ワンチャンあるで
— reew (@sortreew) December 13, 2015

それでは～(pelkira氏曰く最後にそれではと付けるのは神の影響らしい)