Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-04-22TCO2012 Round2A

  • 300:WA(+50), 450:Opened, score:50.00, rank:430, rating:2170(-23)
  • cafelierさんと同じ部屋だった
  • なかなかに厳しい問題セットだった・・・
  • 最後の3分間チャレンジができなかったとかで、無効試合になるかもしれないらしい → ならなかった

TCO2012 Round2A 300 SwitchesAndLamps

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

コーディングフェーズ

以下の2つの問題に分けて考えればいい

  1. 与えられた情報から、スイッチとランプをこれ以上分割できないグループに分割する
  2. 各グループを更にスイッチ・ランプ1個ずつのグループまで分割するための最小テスト数を求める

時間をかけた挙句、1,2ともに間違った解答を出してしまいチャレンジされる


後で

1のほうは、実は縦に見て全く同じ結果のものを集めればいいだけだったりする

つまり、1回目のテストがY、2回目がN、3回目がYのスイッチがあったとすると、それと同じグループに入れるスイッチは、やはり1回目のテストがY、2回目がN、3回目がYのスイッチである。

同様に、ランプの全く同じパターンのものを集める。

1つのグループ内で、スイッチとランプの数が違っていたら-1。


2のほうは、とりあえず全てのグループに対し、並列で試験ができるので、一番スイッチ数の多いグループだけを考えればいい。

並列で試験できることを考えると、試験数を最小にするには、グループをYとNで2分割することである

分かれた2つのグループに対し同時に試験ができるから、さらに大きい方を2分割して・・・と続けていくと、いつかスイッチ数が1になる

これにかかる回数を出せばOK


ソースコード

試験結果の比較はstringでやればいいのだが、何かあまり整理しきれてないときに書いたコード

任意のスイッチorランプのペアに対して、1つでも結果が異なる試験があれば別グループという判定をしている

class SwitchesAndLamps {
public:
	int calc(ll cnt) {
		int res=0;
		while(cnt>1) {
			cnt=(cnt+1)/2;
			res++;
		}
		return res;
	}

	int theMin(vector <string> sw, vector <string> lmp) {
		int res;
		int esz=sw.size(), n=sw[0].size();

		int conn[102][102];
		for(int i=0; i<n*2; i++) for(int j=0; j<n*2; j++) conn[i][j]=1;
		for(int i=0; i<esz; i++) {
			for(int j=0; j<n; j++) {
				for(int k=j+1; k<n; k++) {
					if(sw[i][j]!=sw[i][k]) conn[j][k]=conn[k][j]=0;
					if(lmp[i][j]!=lmp[i][k]) conn[n+j][n+k]=conn[n+k][n+j]=0;
				}
				for(int k=0; k<n; k++) {
					if(sw[i][j]!=lmp[i][k]) conn[j][n+k]=conn[n+k][j]=0;
				}
			}
		}

		res=0;
		vector <int> used(n*2);
		for(int i=0; i<n; i++) {
			if(used[i]) continue;
			used[i]=1;
			int swcnt=1, lmpcnt=0;
			for(int j=i+1; j<2*n; j++) {
				if(!conn[i][j]) continue;
				assert(!used[j]);
				used[j]=1;
				if(j<n) swcnt++;
				else lmpcnt++;
			}
			if(swcnt!=lmpcnt) return -1;
			res=max(res, calc(swcnt));
		}

		return res;
	}
};

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