Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-12-22SRM527 Div1

  • 275:193.05, 450:274.22, score:467.27, rank:117, rating:2198(+37)
  • 史上最高に2199というイケてるスコアに近づいた

SRM527 Div1 275 P8XGraphBuilder

| 01:20 | SRM527 Div1 275 P8XGraphBuilder - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM527 Div1 275 P8XGraphBuilder - SRM diary(Sigmar) SRM527 Div1 275 P8XGraphBuilder - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

Treeになるということで、何かメモ化再帰すればいいんだろう

多少悩みながら以下の方針を思いつく

  • あるTreeが既に途中まで作られているとして、リーフ数と未使用のエッジ数を状態とする
  • 適当なリーフに総当たりで子をくっつけて新しいTreeを作る

何か本番はやっぱりテンパッてしまうようで随分時間がかかってしまった


ソースコード

const int INF=1000000000;
int memo[52][52];

class P8XGraphBuilder {
public:
	int n;
	vector <int> scores;

	int rec(int cnode, int edge) {
		int res=0;
		if(cnode==0) return 0;
		if(memo[cnode][edge]>=0) return memo[cnode][edge];

		for(int i=0; i<=edge; i++) {
			res=max(res, rec(cnode-1+i, edge-i)+scores[i]);
		}

		memo[cnode][edge]=res;
		return res;
	}

	int solve(vector <int> scores_) {
		int res=0;

		scores=scores_;
		n=scores.size();

		memset(memo, -1, sizeof(memo));
		for(int i=1; i<=n; i++) {
			int tres=scores[i-1];
			tres+=rec(i, n-i);
			res=max(res, tres);
		}
		return res;
	}
};

SRM527 Div1 450 P8XMatrixRecovery

| 01:20 | SRM527 Div1 450 P8XMatrixRecovery - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM527 Div1 450 P8XMatrixRecovery - SRM diary(Sigmar) SRM527 Div1 450 P8XMatrixRecovery - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

辞書順最小ということで、やり方は限られてくると思う

何らかDPしながら最小のものを順番に作っていくとか、独立に1つずつ決められるとか、Greedyに1つずつ決められるとか

DPはちょっと考えても無理そう。方針が全く思いつかない。

独立に決めるのは・・・どう考えても他の値を決めると選択肢が狭まったりするから独立ではなさそう

Greedyにできるか・・・ある「?」を0か1にしたとき、その状態で解があるかどうかが分かれば良い

どう見てもカラムの二部マッチングである

しかし二部マッチングってあまり使わないので計算量を忘れてしまった。

えーと・・・

自分のライブラリはエドモンズカープだったはずだ

エドモンズカープはO(V・E^2)だった

フルメッシュでE=V^2とするとマッチングだけでO(V^5)、さらに「?」の数だけやるのでO(N^7)=無理

いや、よく見ると自分のライブラリはエドモンズカープではなかった

帯域幅優先探索で増加道を決めるフォードファルカーソンで書かれている

こんなもん、二部マッチングみたいな帯域1しかないやつに使っても遅くなるだけじゃないのか・・何だこのライブラリは

うーむしかしさすがに最悪計算量をあまりに最悪に取りすぎている気もする・・・

他に解き方も思いつかないので書くしかない

書いた

全部「?」のパターンでテスト

0.5sくらいで終わる

良かった・・・・・・・

提出


ソースコード

さすがに二部マッチングは書きなおしたほうがいい気がする。。。

O(V^3)の最大流アルゴリズムがあるようなので後日確認しておきたい。

vector <int> val;
vector <int> dad;
vector <vector <bool> > am;
vector <vector <int> > eflow, esize;
const ll unseen=-2000000000;
const int INF=2000000000;

class P8XMatrixRecovery {
public:
	bool visit(int sc, int sk) {
		int m, c;
		priority_queue <pair<int, int> > q;
		pair <int, int> qt;

		q.push(make_pair(INF, sc));
		dad[sc]=sc; val[sc]=INF;
		while(!q.empty()) {
			qt=q.top(); q.pop();
			m=qt.second;
			if(val[m]>qt.first) continue;
			for(int i=0; i<(int)am[m].size(); i++) {
				if(m==i || !am[m][i]) continue;
				c=-eflow[m][i];
				if(esize[m][i]>0) c+=esize[m][i];
				c=min(qt.first, c);
				if(val[i]<c && c>0) {
					q.push(make_pair(c, i));
					val[i]=c; dad[i]=m;
					if(i==sk) return true;
				}
			}
		}

		return false;
	}

	void maxflow(int sc, int sk) {
		int x, y;

		while(visit(sc, sk)) {
			y=sk; x=dad[sk];
			while(y!=sc) {
				eflow[x][y]+=val[sk];
				eflow[y][x]-=val[sk];
				y=x; x=dad[y];
			}
			dad.assign(dad.size(), -1);
			val.assign(val.size(), unseen);
		}
	}

	vector <string> solve(vector <string> row, vector <string> col) {
		vector <string> res=row;
		int h=row.size(), w=col.size();
		int scsize=w, sksize=w;
		int sc, sk;

		sc=0; sk=scsize+sksize+1;

		for(int r=0; r<h; r++) {
			for(int c=0; c<w; c++) {
				if(row[r][c]!='?') continue;
				row[r][c]='0';

				dad.assign(scsize+sksize+2, -1);
				val.assign(scsize+sksize+2, unseen);
				am.assign(scsize+sksize+2, vector <bool>(scsize+sksize+2, false));
				esize.assign(scsize+sksize+2, vector <int>(scsize+sksize+2, 0));
				eflow.assign(scsize+sksize+2, vector <int>(scsize+sksize+2, 0));

				for(int i=0; i<scsize; i++) {
					am[sc][i+1]=true;
					esize[sc][i+1]=1;
					am[i+1][sc]=true;
					esize[i+1][sc]=-1;
				}
				for(int i=0; i<sksize; i++) {
					am[i+scsize+1][sk]=true;
					esize[i+scsize+1][sk]=1;
					am[sk][i+scsize+1]=true;
					esize[sk][i+scsize+1]=-1;
				}

				for(int i=0; i<w; i++) {
					for(int j=0; j<w; j++) {
						int ok=true;
						for(int k=0; k<h; k++) {
							if(row[k][i]!='?' && col[j][k]!='?' && row[k][i]!=col[j][k]) ok=false;
						}
						if(ok) {
							am[i+1][j+scsize+1]=true;
							esize[i+1][j+scsize+1]=1;
							am[j+scsize+1][i+1]=true;
							esize[j+scsize+1][i+1]=-1;
						}
					}
				}

				maxflow(sc, sk);
				int cnt=0;
				for(int i=1; i<scsize+1; i++) {
					if(am[sc][i]) cnt+=eflow[sc][i];
				}
				if(cnt<w) row[r][c]='1';
			}
		}

		return row;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111222