JOI 予選 2015/2016 参加記

競プロ

せっかくはてなブログを作ったのこのあいだのJOI予選について書きます。
ソースコードはあまりに汚い上，間違えてると思うので読まないほうが良いです。


すいません読まないでください！なんでもしますから！


9~10月

競プロの勉強会で知り合った人にJOI参加を勧められたのでとりあえず参加を志す。

今までAtCoderメインでやっていた競プロをAOJでJOIの過去問を解くようにした。

「DPわかんない」って週一で言うようになる。

11月

問題4から先がネックだと思ったので類似問題(DP中心)を解くようにした。

Taxis | Aizu Online Judge

とか

Schedule | Aizu Online Judge

が難しかったけどいい問題だと思った。

「bitDP頭良いなぁ」とか思ってたら期末試験の1週間前に突入したので競プロをしなくなった。

期末は12月8日までだったのでJOIまで残り5日ってところまでこの記事も飛びます。

あと競プロに集中するためにﾂｲ禁(知り合いしかフォローしてない別アカは見てた。)をしたけどこれといって特に意味はなかった。

もう二度とやらねぇ。


12月8~12日

問題5, 6を解くようになったけど難しいのは本当に難しいから解説みたり他人のコード見て実装するだけ。

「こんなん本番で思いつけなんて無茶じゃね？？」ってなる。

JOIの間にTwitterやって不正にならないようにこのあたりからなるべくTwitterやその他SNSに触れないようにしてた。
つもり。

12月13日が近づくにつれて”今更問題解いたところでどうにもならないだろ感”が襲ってくるようになってきたのでそんなにコーディングしてなかった。


12月13日 午前

No.314 ケンケンパ - yukicoder
を解く。
割と簡単なDPだったけどバグで溢れかえったので自信を失った。


予選

問題1

やるだけ。
なんだけど問題よく見てなくて思いのほか時間がかかってしまった。

int n[4];

int main(){
	int maxi=0;
	REP(i, 4){
		cin >> n[i];
	}
	sort(n, n+4);
	FOR(i, 1, 4) maxi+=n[i];
	
	int maxi2=0;
	int p=0;
	REP(i, 2){
		cin >> p;
		maxi2=max(maxi2, p);
	}
	
	cout << maxi+maxi2 << endl;
}

問題2

これもやるだけ。
なんだけど問題が分かりにくいなぁと思った。

問題1より時間はかからなかった。

int n, m;
vector<int> a(100);

int main(){
	cin >> n >> m;
	REP(i, n) cin >> a[i];
	
	FOR(j, 1, m+1){
		REP(i, n-1){
			if((a[i]%j)>(a[i+1]%j)){
				swap(a[i], a[i+1]);
			}
		}
	}
	
	REP(i, n) cout << a[i] << endl;
}

問題3

プーチン。
全探索した。
よくわかんないけどあってると思う。

vector<string> str(50);
int n, m;

int p(int h, bool w, bool b, bool r){
	if(h==n){
		if(!w||!b||!r) return INF;
		return 0;
	}
	
	int ret=0;
	
	if(!w&&!b&&!r){
			int W=0;
			REP(j, m){
				if(str[h][j]!='W') W++;
			}
			ret+=W;
			ret+=p(h+1, 1, b, r);
		}
		
		if(w&&!b&&!r){
			int W=0;
			int B=0;
			REP(j, m){
				if(str[h][j]!='W') W++;
				if(str[h][j]!='B') B++;
			}
			ret+=min(p(h+1, 1, 0, r)+W, p(h+1, 1, 1, r)+B);
			
		}
		
		if(w&&b&&!r){
			int R=0;
			int B=0;
			REP(j, m){
				if(str[h][j]!='R') R++;
				if(str[h][j]!='B') B++;
			}
			ret+=min(p(h+1, 1, 1, r)+B, p(h+1, 1, 1, 1)+R);
		}
		
		if(w&&b&&r){
			int R=0;
			REP(j, m){
				if(str[h][j]!='R') R++;
			}
			ret+=p(h+1, 1, 1, 1)+R;
		}
		
		return ret;
}

int main(){
	cin >> n >> m;
	REP(i, n){
		cin >> str[i];
	}
	
	cout << p(0, 0, 0, 0) << endl;
}

問題4


問題読んですぐに「これDPじゃないなぁ」って分かった。うれしい。
問題4でDPじゃないのはエラい久しぶりなことらしい。

頭悪いので愚直にシミュレートしたらケース1しか答えが出せなかった。

お昼ごはんを食べながら解いてた。
この時食べてたサンドイッチはやたらとおいしかった気がする。

int n, t, q;
vector<llong> a(100000);
vector<llong> x(100000);
vector<bool> d(100000, 0);
vector<bool> c(100000);
map<llong, llong> m;

int main(){
	cin >> n >> t >> q;
	REP(i, n){
		int f;
		cin >> a[i] >> f;
		d[i]= (f==1 ? 1 : 0);
	}
	REP(i, q){
		cin >> x[i];
		x[i]--;
	}
	
	FOR(i, 1, t+1){
		REP(j, n){
			if(d[j] && !c[j]){
				if(m.find(a[j]+1)!=m.end()){
					c[j]=1;
					c[m[a[j]+1]]=1;
					m.erase(a[j]);
					a[j]++;
				}
				else{
					m[a[j]+1]=j;
					m.erase(a[j]);
					a[j]++;
				}
			}
			else if(!d[j] && !c[j]){
				if(m.find(a[j]-1)!=m.end()){
					c[j]=1;
					c[m[a[j]-1]]=1;
					m.erase(a[j]);
					a[j]--;
				}
				else{
					m[a[j]-1]=j;
					m.erase(a[j]);
					a[j]--;
				}
			}
		}
	}
	
	REP(i, q){
		cout << a[x[i]] << endl;
	}
}

問題5

問題文がファンタジーすぎて「は？」ってなったけどよく読んだらまったくコレ。

探索＋ダイクストラっていう解き方はあってるっぽいけど実装が悪すぎて答えだすのに時間がかかりすぎる。

ベルマンフォードでも間に合うらしい。

int n, m, k, s;
int p, q;
vector<int> c(100000, 0);
vector<vector<bool> > v(100000, vector<bool>(100000, 0));

int bfs(int z){
  queue<pair<int, int> > q;
  q.push(make_pair(z, s));
  vector<bool> f(n, 0);
  f[z]=1;
  
  while(!q.empty()){
    int u=q.front().first;
    int rr=q.front().second;
    q.pop();
    
    if(rr<=0) continue;
    
    REP(i, n){
      if(v[u][i] && !f[i]){
		if(c[i]==0) c[i]=1;
        f[i]=1;
        if(rr-1>=0) q.push(make_pair(i, rr-1));
      }
    }
  } 
}

int dijkstra(int s){
	priority_queue<pair<int, int> > pq;
	pq.push(make_pair(0, s));
	vector<bool> f(n, 0);
	vector<llong> d(n, INF);
	d[s]=0;
	
	while(!pq.empty()){
    	int u=pq.top().second; pq.pop();
    	f[u]=1;
		
		if(u==n-1) return d[u]-c[n-1];
		
    
    	REP(i, n){
			if(c[i]==-1) continue;
      		if(!f[i] && v[u][i]){
        		if(d[i]>d[u]+c[i]){
        		  d[i]=d[u]+c[i];
        		  pq.push(make_pair(d[i]*(-1), i));
        		}
      		}
    	}
	}
	
	return d[n-1]-c[n-1];
}

int main(){
	cin >> n >> m >> k >> s;
	cin >> p >> q;
	
	int t[k];
	REP(i, k){
		ifs >> t[i];
		t[i]--;
		c[t[i]]=2;
	}
	
	REP(i, m){
		int f, t;
		ifs >> f >> t;
		f--; t--;
		v[f][t]=v[t][f]=1;
	}
	
	REP(i, k) bfs(t[i]);
	
	REP(i, n){
		if(c[i]==2) c[i]=-1;
		else if(c[i]==1) c[i]=q;
		else c[i]=p;
	}
	
	cout << dijkstra(0) << endl;
}

問題6

bitDPだなぁと思ったけど実装できず。
よってソースコードなし。

ケース1は手で解いたけど間違えてた。
やめたくなりますよ～。

予選終了後

Twitterで答え合わせをするなどした。
一応提出ミスとかそもそも答え間違えてるとかなければ380点っぽいです。
ボーダー何点なんかなぁ…

12月18日 追記

問題5のケース2が間違っていたので，360点でした。
ボーダーが360点らしいのでギリギリAランクで本選に出場できることになりました。
本選まであと2ヶ月弱はあるので精進していきたい。