Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2012-04-22TCO2012 Round2A

TCO2012 Round2A 450 CucumberWatering

| 17:48 | TCO2012 Round2A 450 CucumberWatering - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2012 Round2A 450 CucumberWatering - SRM diary(Sigmar) TCO2012 Round2A 450 CucumberWatering - SRM diary(Sigmar) のブックマークコメント

コーディングフェーズ

どう見てもDPっぽい

テレポートポイントはcucumberの上にしか置かなかったとしても問題なさそうなのでそうする

普通にやれば、水をやる順番に進めたいところだが、そうするとどのcucumberの上に置いたか記憶するので2^50とかになるので無理

とすると、x座標で左から順にテレポートを置いていくとか考えるわけです

前にテレポートを置いた場所をptelとすると、現在の位置ctelに置いたとき、ptel~ctel間のcucumberはどんな距離を加算すれば良いでしょう

この辺で整理できなくなって時間切れになってしまった


後で

ptel~ctelの間にcucumber iがあったとき、次に水をやるcucumber i+1との距離と、前に水をやったcucumber i-1との距離をそれぞれ加算する

しかし、このとき基本的に最寄りのテレポートを経由して行くことにする。

ただし、i-1(またはi+1)がptel~ctelの間にあるときは、直接歩いたほうが早いかもしれない。

なので、その時は早いほうを採用する。

なお、i-1(またはi+1)がptel~ctelの間にないときは、必ずテレポートを経由して行っても直接歩くより時間がかかることはない。

(同じテレポートから出てくることも可能なため)

ということでDPが書けるので書く

かなり書くのしんどい


上位の人が軒並み200点台の中で、Petr見たら370点とかだった

アルゴリズム力もさることながら、ややこしいコードを素早く書く能力がずば抜けている・・・

Petr伝説


ソースコード

const ll INF=1000000000000000000LL;

class CucumberWatering {
public:
	long long theMin(vector <int> xx, int K) {
		long long res;
		int n=xx.size();
		vector <ll> x;
		x.push_back(-10000000000LL);//番兵(左端のテレポートポイント)
		for(int i=0; i<n; i++) x.push_back(xx[i]);
		x.push_back(10000000000LL);//番兵(右端のテレポートポイント)

		vector <pair <ll, int> > px;
		for(int i=0; i<n+2; i++) {
			px.push_back(make_pair(x[i], i));
		}
		sort(px.begin(), px.end());

		vector <int> rx(n+2);
		for(int i=0; i<n+2; i++) rx[i]=px[i].second;

		ll dp[53][53][53];
		for(int i=0; i<53; i++) for(int j=0; j<53; j++) for(int k=0; k<53; k++) dp[i][j][k]=INF;
		dp[1][0][0]=0;
		for(int ctel=1; ctel<=n+1; ctel++) {
			for(int ptel=0; ptel<ctel; ptel++) {
				for(int k=0; k<=min(ctel, K); k++) {
					if(ctel<=n) dp[ctel+1][ptel][k]=min(dp[ctel+1][ptel][k], dp[ctel][ptel][k]);
					if(ctel<=n && k==K) continue;//右端の番兵には必ずテレポートを設置する
					ll nval=dp[ctel][ptel][k];
					if(nval>=INF) continue;
					ll ptelpos=x[rx[ptel]], ctelpos=x[rx[ctel]];
					for(int i=ptel+1; i<=min(n, ctel); i++) {
						ll cpos=x[rx[i]];
						ll tdist=min(abs(cpos-ptelpos), abs(cpos-ctelpos));
						if(rx[i]>1) {
							ll ppos=x[rx[i]-1];
							if(ptelpos<ppos && ppos<ctelpos) {
								ll odist=abs(cpos-ppos);
								ll ptdist=min(abs(ppos-ptelpos), abs(ppos-ctelpos));
								if(odist<tdist+ptdist) nval+=odist;
								else nval+=tdist;
							} else nval+=tdist;
						}
						if(rx[i]<n) {
							ll npos=x[rx[i]+1];
							if(ptelpos<npos && npos<ctelpos) {
								ll odist=abs(cpos-npos);
								ll ntdist=min(abs(npos-ptelpos), abs(npos-ctelpos));
								if(odist<tdist+ntdist) nval+=0;//ppos側で加算したはず
								else nval+=tdist;
							} else nval+=tdist;
						}
					}
					dp[ctel+1][ctel][k+1]=min(dp[ctel+1][ctel][k+1], nval);
				}
			}
		}

		res=INF;
		for(int i=0; i<n+2; i++) for(int j=0; j<=K+1; j++) res=min(res, dp[n+2][i][j]);
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120422