chigichan24に人権はあるだろうか,いやない

競技プログラミングやってます。

joi2016予選参戦記

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


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


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

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

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



ボーダー予想は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はすごいと思った.



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