ICPC2016 国内予選コード置き場 - あったこといろいろ

ICPC2016 国内予選の問題を解いたコードを載せておきます。
解法の説明はざっくりです。

参加記はこっちです。
ICPC2016 国内予選参加記 - あったこといろいろ

問題文はこっちです。
All Problems

A問題

ソートして、隣り合う要素の差の最小値を出力

#include"bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(a) (a).begin(),(a).end()
#define INF 999999999

int main(){
	int n;
	while(cin>>n&&n){
		vector<int> data(n);
		rep(i,n)cin>>data[i];
		
		sort(all(data));
		int ans = INF;
		rep(i,n-1){
			ans = min(ans,data[i+1]-data[i]);
		}
		cout<<ans<<endl;
	}
}

B問題

毎回、暫定1位と2位の得票数を調べ、「1位の得票数 > 2位の得票数+残りの票数」を満たした時が当選確実。

#include"bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)

int main(){
	int n;
	
	while(1){
		cin>>n;
		if(n == 0) break;
		
		int a[200] = {0};
		vector<string> v(n);
		
		bool f=false;
		
		rep(i, n){
			cin>>v[i];
			if(f)continue;

			a[v[i][0]]++;
			
			char ch='0';
			int count1 = 0, count2 = 0;
			for(int j='A';j<='Z';j++){
				if(a[j] > count1){ count2 = count1; count1 = a[j]; ch = (char)j; }
				else if(a[j] > count2) count2 = a[j];
			}
			
			if(count2 + n-i-1 < count1){cout<<ch<<" "<<i+1<<endl; f=true;}
		}
		if(!f)cout<<"TIE"<<endl;
	}
}

C問題

エラトステネスのふるいっぽく配列を埋めながらシュミレーション。
コードはチームメイトが書いたので、ここには貼りません。

D問題

状態 dp[i][j]

区間(i,j)で最適にブロックを取り除いた時の、取り除けるブロックの個数
そのとき、区間(i,j)に残っているブロックに書かれた数字の列

遷移

dp[i][j] = min( dp[i][k] + dp[k+1][j] - deleted , dp[i][j] )

区間(i,j)での最適な解は、区間(i,k) と区間(k+1,j) の組み合わせで求められる。
deletedは、dp[i][k]の数列の右端と dp[k+1][j]の数列の左端の差が1以下なら2、そうでなければ0。
kは区間(i,j)の間のどこを区切りに2つの区間に分けるかを表し、列 i+1 ~ j-1 の範囲で変化させる。
数字の列も適当にマージする

状態に数列を持っているので、コピーコストなどが原因で少し実行に時間がかかる。

#include"bits/stdc++.h"
using namespace std;
typedef pair<int,int> pii;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define INF 999999999

vector<int> w;
struct st{ int val; vector<int> elm; };

st dp[310][310];
st dfs(int left,int right){
	if(dp[left][right].val!=INF) return dp[left][right];
	if(left==right) return dp[left][right] = st{1,vector<int>(1,w[left])};

	int n = right-left+1;
	st mini = st{INF,vector<int>(0)};
	rep(i,n-1){
		st l = dfs(left,left+i);
		st r = dfs(left+i+1,right);
		int tmp = l.val+r.val;
		
		bool deleted=false;
		if( l.elm.size() && r.elm.size() ){
			if(  abs( l.elm[l.elm.size()-1] - r.elm[0] )<=1  ){
				tmp-=2;
				deleted=true;
			}
		}
		
		if(mini.val>tmp){
			vector<int> vec;
			vec.reserve(l.elm.size()+r.elm.size());
			copy(l.elm.begin()		,l.elm.end()-deleted    ,back_inserter(vec));
			copy(r.elm.begin()+deleted	,r.elm.end()		,back_inserter(vec));
			
			mini = st{tmp,vec};
		}
	}
	return dp[left][right] = mini;
}


int main(){
	int n;
	while(cin >> n&&n){
		w.resize(n);
		rep(i, n) cin >> w[i];
		rep(i,310)rep(j,310)dp[i][j]=st{INF,vector<int>(0)};
		st res = dfs(0,n-1);
		cout<<n-res.val<<endl;
	}
}