Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-06-19TCO2011 Round1

TCO2011 Round1 1000 IPv444

| 17:19 | TCO2011 Round1 1000 IPv444 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2011 Round1 1000 IPv444 - SRM diary(Sigmar) TCO2011 Round1 1000 IPv444 - SRM diary(Sigmar) のブックマークコメント

Problem Statement

最近APNICのIPv4アドレス在庫が枯渇しましたから、それにちなんだ問題かな

現実のIPv4アドレスはトレードされるということはないと思いますが・・・


コーディングフェーズ

価値の高い順に売っていって、既に売った分を数えないように計算しようと思ったが全然うまく書けなかった

1時間弱もあってこれでは・・・

もう少し戦略的に書き方を練るようにしないとダメだな・・


後で

あまりいい書き方が思いつかなかったのでtop submissionを見てしまいました

C++のtomekkulczynski氏の書き方が分かりやすかったです。

4つの数字の左側から分岐して、dfs的にパターンを列挙し、そのパターンで最も価値の高いものを売るようにする

JavaのPetr氏も見たけど、書き方は違うが同じような感じで、単に全探索している感じ

パターン的には高々50^4しかないので、計算量も大丈夫

しかし、Petr氏は各パターンが有効な範囲かの判定と各パターンの最大価値算出を同一変数で書いたり、出現する数字を種類数で圧縮したりとやや巧妙な書き方が多いので何でそんな早く書けるのか不思議・・・


今回はうまく全探索が書けるかというのがポイントだったかな


ソースコード

tomekkulczynski氏的なやり方

vector <string> strspltos(string str, char delim) {
	vector <string> res;
	stringstream ss(str);
	string s;
	while(getline(ss, s, delim)) {
		if(ss.fail()) continue;
		res.push_back(s);
	}
	return res;
}

class IPv444 {
public:
	ll rec(int d, vector <pair <int, vector <int> > > & reqp) {
		ll res=0;

		if(d==4) {
			int maxprice=0;
			for(int i=0; i<(int)reqp.size(); i++) {
				maxprice=max(maxprice, reqp[i].first);
			}
			return maxprice;
		}

		set <int> candvals;
		for(int i=0; i<(int)reqp.size(); i++) {
			candvals.insert(reqp[i].second[d]);
		}

		for(set <int>::iterator sti=candvals.begin(); sti!=candvals.end(); sti++) {
			int candval=*sti;
			vector <pair <int, vector <int> > > nreqp;
			for(int i=0; i<(int)reqp.size(); i++) {
				if(reqp[i].second[d]==-1 || reqp[i].second[d]==candval) nreqp.push_back(reqp[i]);
			}
			if(candval==-1) res+=rec(d+1, nreqp)*(1000-candvals.size()+1);
			else res+=rec(d+1, nreqp);
		}

		return res;
	}

	long long getMaximumMoney(vector <string> req, vector <int> price) {
		long long res=0;
		int n=req.size();

		vector <pair <int, vector <int> > > reqp;
		for(int i=0; i<n; i++) {
			vector <string> vs=strspltos(req[i], '.');
			vector <int> vi;
			for(int j=0; j<4; j++) {
				if(vs[j][0]=='*') vi.push_back(-1);
				else {
					int v;
					stringstream ss(vs[j]);
					ss >> v;
					vi.push_back(v);
				}
			}
			reqp.push_back(make_pair(price[i], vi));
		}

		res=rec(0, reqp);

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