JOI2015参加記

さて、本日JOI予選の結果がメールで送られてきました。
6問に手を出し（全てアルゴリズムは分かった）、うち６問目は実装にバグが残って実行も出来ずに時間切れでした。ということで５完。

…と思ってました。13日の22:00までは。
一応と思って解答が公開されるのを待って全てダウンロード、diffを使って確かめてみると、問題3と5につまらないミスがあったことが発覚。死亡しました。

ということで340点。ボーダーは360点らしく、ギリギリアウトです。
ここで、「問題6を無理に満点解法狙うんじゃなくて、ケース1に特化した解法で書いておけば良かった…」と後悔してももう遅い。1年の努力をしょうもないミスで水の泡に変えてしまった自分でした。
しっかし、1番気に食わないのはボーダーが360ということは問題4がO(N^2)解法でも問題3まで全部合っていれば本戦に行けてしまうということですね…
しかし、終わったことは仕方ない。自分の実装力と運が不足していた。

さて、折角なので全部コードも出して解説しておきたいと思います。

問題1：科目選択 (Selecting Subjects)

この問題、入力の内容を読まずに解きました。最初に全教科を足し、そこから理科の最低点、社会の最低点を引くだけです。
…解けないやつが居るのか？という感じでした。

#include <bits/stdc++.h>
using namespace std;
int main(){
	int a,b,c,d,e,f;	cin>>a>>b>>c>>d>>e>>f;
	cout<<a+b+c+d+e+f-min(min(a,b),min(c,d))-min(e,f)<<endl;
	return 0;
}

問題2:ゼッケンの交換 (Swapping Bibs)

N,M≦100なので愚直にシミュレーションしてやりましょう。O(NM)。

#include <bits/stdc++.h>
using namespace std;
int main(){
	int n,m;	cin>>n>>m;
	vector<int> a(n);
	for(int i=0;i<n;i++)	cin>>a[i];
	for(int i=1;i<=m;i++){
		for(int j=1;j<n;j++){
			if(a[j-1]%i>a[j]%i)	swap(a[j],a[j-1]);
		}
	}
	for(int i:a)	cout<<i<<endl;
	return 0;
}

問題3:ロシアの旗 (Russian Flag)

これも普通に白の下限、青の下限を全部試してO(N^2M)でもいいのです。しかし、この問題、見た瞬間に「各行に赤青白がいくつあるか」が分かれば列は関係ないことに気付きました。というより気付いてください。
ということで予め各行に赤青白がいくつあるかカウントしてあげてからやればO(N^2)か。

#include <bits/stdc++.h>
using namespace std;
int main(){
	int n,m;	cin>>n>>m;
	vector<int> w(n),b(n),r(n);
	for(int i=0;i<n;i++){
		string s; cin>>s;
		for(int j=0;j<m;j++){
			if(s[j]=='W')	w[i]++;
			else if(s[j]=='R')	r[i]++;
			else if(s[j]=='B')	b[i]++;
		}
	}
	int ans=INT_MAX;
	for(int i=0;i<n-2;i++){//白の境界
		int tmp=0;
		for(int j=0;j<=i;j++)	tmp+=b[j]+r[j];
		for(int j=i+1;j<n-1;j++){//青の境界
			for(int k=i+1;k<=j;k++)	tmp+=w[k]+r[k];
			for(int k=j+1;k<n;k++)	tmp+=w[k]+b[k];
			ans=min(ans,tmp);
		}
	}
	cout<<ans<<endl;
	return 0;
}

ここまで15分しか経って無いし、楽勝！と思ってたんですがね…
上のコード、ケース1しか通りません。理由は簡単。tmpが初期化されずに一方的に増え続けています。
ということでループ内をこんな感じにしてれば本戦に行っていました。

for(int j=i+1;j<n-1;j++){//青の境界
	int tmp2=0;
	for(int k=i+1;k<=j;k++)	tmp2+=w[k]+r[k];
	for(int k=j+1;k<n;k++)	tmp2+=w[k]+b[k];
	ans=min(ans,tmp+tmp2);
}

なんでこの程度の事に気付けなかったんだろ…

問題4:JOI国のお散歩事情 (Walking in JOI Kingdom)

アルゴリズムは一瞬で浮かぶ。でも実装に苦労させられました。
移動前の位置をソートしてあげて、そこから全員衝突を無視して最後の地点まで歩かせる。元の位置関係と逆になっていればその人達は衝突しているはず。衝突地点は2人の座標の平均値なので、衝突地点に合わせて、「ぶつかった」というフラグを立てておく。フラグが立っている人と衝突してたらフラグが立っている方に合わせて上げればOKです。
一応全員の位置のソート、そして家の番号と座標の組み合わせの探索にO(NlogN)です。自分はてっきりfind関数がO(logN)で働いてくれると思っていたので、ケース4であれ？となっていました。仕方無く絶対一致する値があるのでlower_boundに任せたら数秒で終わりました。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<pair<ll,int>> pos;
int main(){
	ll n,t,q;	cin>>n>>t>>q;
	vector<ll> a(n);
	vector<int> d(n);
	for(int i=0;i<n;i++){
		cin>>a[i]>>d[i];
		pos.push_back(make_pair(a[i],d[i]));
	}
	sort(pos.begin(),pos.end());
	vector<ll> endpos(n);
	for(int i=0;i<(int)pos.size();i++){
		endpos[i]=pos[i].first+(pos[i].second==1?1:-1)*t;
	}
	bool stop[n];	memset(stop,0,sizeof(stop));
	for(int i=1;i<(int)pos.size();i++){
		if(stop[i-1]&&endpos[i-1]>endpos[i]){
			endpos[i]=endpos[i-1];	stop[i]=true;
		}
		else if(stop[i]&&endpos[i-1]>endpos[i]){
			endpos[i-1]=endpos[i];	stop[i-1]=true;
		}
		else if(endpos[i-1]>endpos[i]){
			ll change=(endpos[i-1]+endpos[i])/2;
			endpos[i-1]=change;	endpos[i]=change;
			stop[i-1]=true;	stop[i]=true;
		}
	}
	for(int i=(int)pos.size()-1;i>0;i--){
		if(stop[i-1]&&endpos[i-1]>endpos[i]){
			endpos[i]=endpos[i-1];	stop[i]=true;
		}
		else if(stop[i]&&endpos[i-1]>endpos[i]){
			endpos[i-1]=endpos[i];	stop[i-1]=true;
		}
		else if(endpos[i-1]>endpos[i]){
			ll change=(endpos[i-1]+endpos[i])/2;
			endpos[i-1]=change;	endpos[i]=change;
			stop[i-1]=true;	stop[i]=true;
		}
	}
	for(auto i:pos)	cout<<i.first<<" ";
	cout<<endl;
	for(auto i:endpos)	cout<<i<<" ";
	cout<<endl;
	vector<ll> end(n);
	for(int i=0;i<n;i++){
		vector<pair<ll,int>>::iterator it=lower_bound(pos.begin(),pos.end(),make_pair(a[i],d[i]));
		int place=distance(pos.begin(),it);
		end[i]=endpos[place];
	}
	for(int i=0;i<q;i++){
		int x;	cin>>x;	x--;
		cout<<end[x]<<endl;
	}
	return 0;
}

なかなか複雑でしたね。自分もdistanceは知っていながらも初めて使わされました。
posは移動前の座標に移動方向をくっつけたもの、endposはposからT秒経った状態。endはposとaを使って求めたaの人の順に並べた最終地点です。この3つの情報をどうソート前後で組み合わせるかに悩まされました。

問題5:ゾンビ島 (Zombie Island)

がっこうぐらし！からすればゾンビに侵略された島に宿泊出来ないなんて甘いんでしょうけど…
予め危険区域に指定された街がどれか知っておきたいですね。ということでダイクストラです。危険度をゾンビに侵略された島はs+1として、そこから島を1つ渡る毎に危険度が1減るように設定します。そうすると危険地帯でないところの危険度は0。危険度が0か正かで判別できるようになりました。
そうしたら単一始点最短経路問題でしたっけ？になります。自分はダイクストラ大好きなので連続で使用。ただし、危険度=s+1であるところはゾンビに侵略されているので入れません。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[100000];
vector<int> e[100000];
int main(){
	int n,m,k,s;	cin>>n>>m>>k>>s;
	int p,q;	cin>>p>>q;
	vector<int> c(k);
	priority_queue<pair<int,int>> dan;//危険な街にする範囲、始点
	int danger[n];	memset(danger,0,sizeof(danger));//危険かどうか
	for(int i=0;i<k;i++){
		cin>>c[i];	c[i]--;
		dan.push(make_pair(k+1,c[i]));
		danger[c[i]]=k+1;
	}
	for(int i=0;i<m;i++){
		int a,b;	cin>>a>>b;	a--;	b--;
		e[a].push_back(b);	e[b].push_back(a);
	}
	while(!dan.empty()){
		auto it=dan.top();	dan.pop();
		if(it.first==0)	break;
		int d=it.first,from=it.second;
		if(d<danger[from])	continue;
		for(int i=0;i<(int)e[from].size();i++){
			if(danger[e[from][i]]<d-1){
				danger[e[from][i]]=d-1;
				dan.push(make_pair(d-1,e[from][i]));
			}
		}
	}
	for(int i=0;i<n;i++)	dp[i]=INT_MAX;
	priority_queue<pair<int,int>> pq;//ダイクストラ用
	pq.push(make_pair(-0,0));
	while(!pq.empty()){
		auto it=pq.top();	pq.pop();
		ll cst=-it.first,from=it.second;
		if(cst>dp[from])	continue;
		if(from==n-1){
			cout<<cst<<endl;
			return 0;
		}
		for(int i=0;i<(int)e[from].size();i++){
			if(danger[e[from][i]]==k+1)	continue;//ゾンビが侵略済みのため進行不可
			ll add=cst;
			if(e[from][i]!=n-1){
				if(danger[e[from][i]]>0)	add+=q;
				else 	add+=p;
			}
			if(add<dp[e[from][i]]){
				dp[e[from][i]]=add;
				pq.push(make_pair(-add,e[from][i]));
			}
		}
	}
	cout<<dp[n-1]<<endl;
	return 0;
}

出来た！例題通った！大丈夫！と出しました。気付いて下さい、自分。sが使われてないでしょ。
ということでゾンビ島の入力の部分が

for(int i=0;i<k;i++){
	cin>>c[i];	c[i]--;
	dan.push(make_pair(s+1,c[i]));
	danger[c[i]]=s+1;
}

となり、更に2回目のダイクストラの位置が

if(danger[e[from][i]]==s+1)	continue;//ゾンビが侵略済みのため進行不可

となってやっとＡＣ。流石に呆れました。

問題6:屋台 (Food stalls)

これは見た瞬間に「ハイハイbitDPね」の流れでしたね。元々6問目はbitDPだろうと予測してたんです。
ケース1では店が20店舗しか無いらしいので全店舗にbitを割り振れば通ると思います。
他のケースを考えると、下の画像のようなwの字型にbitを取るのが良さそう…と思って実装していたのですが、実装が重い。書き終わった！実行！としたらAbort喰らいました。残り時間5分だったのでそのまま挫折。
これはソースコードがあまりに汚く、自分でも読めるか怪しいので割愛します。（そもそも実行できません。）

現在地点を★とすると、現在地と次の地点で関係があるのはこんなもんでしょう。

しかし、現在の場所より先（左と下）の店には絶対訪れることが出来ません。

よって必要なbitデータは上の五ヶ所でしょう。と考えました。（模範解答はよく見てないので分かりません）
それでもbitデータを3×3のデータに直し、それをもう一度bitデータに戻すなんて荒業をやっているから大変でしたね。

という感じでした。
正直こんな実装ミスで本戦に進めなかった自分を恨んでますね。競技中はWAでないことを祈って出したんですが。
恐らく自分の1代下に4完してくれてる後輩がいるので、そちらの指導でもしようかなと思っています。

今後、競プロは完全に趣味として、受験もあって優先順位はどうしても低くならざるを得ませんが続けようと思っています。
目指せRedCoder。

因みに余談ですが、科学の甲子園といい、日本学生科学賞といい、今回のJOIといい。全部全国の1歩手前（科学賞は予備審査まで行きましたが）でやられているんですよね…まるで呪われているかのよう。