Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-06-19TCO2011 Round1

  • 250:WA(+200), 500:418.97, 1000:Opened, score:618.97, rank:197, rating:2089(+54)
  • 250でコーナーケースミスを出してしまった。痛い。
  • 今回の1000くらいのレベルが解けるようになりたい。

TCO2011 Round1 250 TripleStrings

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

Problem Statement

コーディングフェーズ

どう見てもBとCをそれぞれo専用とx専用のバッファに使うだけ

initのsuffixとgoalのprefixが等しくなるまでBやCに詰め込めば良い

簡単だな

書いた→サンプル合わない

答えを2倍しないといけなかった(←ここで2箇所修正が必要なのに1箇所しか修正しなかった)

サンプル合った→出した


チャレンジフェーズ

何気なく開いた人のコードに、最後にinitの長さ*2を返すというのが見える

そういえば自分は最後にinitの長さを返していたような気がする

これは大丈夫なのか・・・

・・・

・・・

大丈夫ではない。{"xoxo", "xxoo"}で落ちる

まずい。

同じミスをしてる人を探す

いた。落とす

またいた。落とす。

合計5人落とした

最後時間なくて適当に投げたら2人ミスった。もったいなかった。

チャレンジ運が良かったから被害が少なく済んだけど、今回は非常に良くないミスをしてしまった。。。


ソースコード

修正済みコード

class TripleStrings {
public:
	int getMinimumOperations(string init, string goal) {
		int n=init.size();

		for(int i=0; i<n; i++) {
			if(init.substr(i)==goal.substr(0, n-i)) return i*2;
		}
		return n*2;//ここでreturn nにしていた
	}
}; 

TCO2011 Round1 500 MuddyRoad

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

Problem Statement

コーディングフェーズ

これは、次がmuddyであれば、その次がmuddyかどうかに関わらず、ジャンプしたほうが良いよね

(そのほうが早く連続するmuddyの区間を抜けられるから)

それから、次がmuddyでなければ、無条件にそこを通れば良いよね

(muddy区間のぎりぎり手前でジャンプしたほうが良いだろうから)

という戦略に基づいて、道iを通る確率をdpで求める

で、道iにいるときに、次とその次が両方ともmuddyだった場合のみ、muddyの道を通ることになるわけだ

ということでコーディングする

サンプル合った

比較的すぐ解けた!いい感じ。


ソースコード

class MuddyRoad {
public:
	double getExpectedValue(vector <int> road) {
		double res=0;
		int n=road.size();

		double dp[52];
		memset(dp, 0, sizeof(dp));
		dp[0]=1;
		for(int i=0; i<n-2; i++) {
			dp[i+1]+=dp[i]*(1.-(road[i+1]/100.));
			dp[i+2]+=dp[i]*(road[i+1]/100.);
			res+=dp[i]*(road[i+1]/100.)*(road[i+2]/100.);
		}
		return res;
	}
};

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