Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-07-01SRM474 Div1

SRM474 Div1 250 RouteIntersection

| 23:55 | SRM474 Div1 250 RouteIntersection - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM474 Div1 250 RouteIntersection - SRM diary(Sigmar) SRM474 Div1 250 RouteIntersection - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→うーん・・・座標をvectorで保存してシミュレーションするだけではないのか、これは・・

→通った点の座標をsetに入れて、移動した数+1より小さければNOT VALIDかな

→書いてみる

→あ、、だめだ、よく見たら次元の最大は10億なのでvectorで表せない

→といっても50個しか点が出てこないので、とりあえず出現する次元にmapで適当にIDをつけてしまおう

→書く→サンプル通る

→mapを使うところ以外は難しいところはない。少し簡単すぎるので不安。。引数Nを使わないというのも大丈夫か、これ・・

→5分ほどかけてコーナーケースなどをチェック

→問題ない。提出

→500へ


チャレンジフェーズ

→10億個vectorを確保しようとしてる人はいないかな・・・

→一人もいない。みんな優秀だなあ。


システムテスト

→Passed


以下、ソースです。

class RouteIntersection {
public:
	string isValid(int N, vector <int> coords, string moves) {
		string res;
		int ps=coords.size();
		vector <int> co(ps, 0);
		set <vector <int> > st;
		map <int, int> cotoi;

		int id=0;
		for(int i=0; i<ps; i++) {
			if(!cotoi.count(coords[i])) cotoi[coords[i]]=id++;
		}

		st.insert(co);
		for(int i=0; i<ps; i++) {
			if(moves[i]=='+') co[cotoi[coords[i]]]++;
			else co[cotoi[coords[i]]]--;
			st.insert(co);
		}

		if((int)st.size()<ps+1) res="NOT VALID";
		else res="VALID";

		return res;
	}
};

SRM474 Div1 500 TreesCount

| 23:55 | SRM474 Div1 500 TreesCount - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM474 Div1 500 TreesCount - SRM diary(Sigmar) SRM474 Div1 500 TreesCount - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→何だろ・・DPっぽいなあ

→どのエッジを削るか、DPしてみるか・・・

→ダメだ、計算量が多すぎる

→どのエッジを使うか、DPしてみるか・・・

→ダメだ、計算量が多すぎる

→順番を変えたりしたらいけるんじゃないか

→ダメだ、どう考えても計算量が減らせない

→うーん・・色々考えていたら30分も経ってしまった

DPばかり考えるとダメだな。。こういうときは、他のアプローチを試さなければ・・

→とりあえずダイクストラで最短経路を求めてみるか

→実はあるノードに同じコストで到達できる数を数えて適当に掛けあわせれば答え出るのでは

→何を数えれば良いか・・・ん・・全ノードにつき、同コストで到達する親の数を数えれば良いか

→あとは、全ノードの親の数を掛けあわせれば、それが解となりそうだ

→合ってるのかな。とりあえず書いてみよう。

→書く→サンプル通る

→10分くらいで書けてしまった。普通のダイクストラに、親の数を数える1文を追加しただけだし、実装が簡単すぎる。怪しすぎる・・・

→うーん・・頭が回らない。。アルゴリズムは合ってると思うんだが・・

→とりあえず提出

→・・・やっぱり合ってるよね。。(不安)


チャレンジフェーズ

→何度か攻撃されるものの耐える。

→意外と普通に通るかもしれんなぁ。


システムテスト

→Failed

→やっぱり。。。(泣)何を間違ったんだろう。

→あーーー・・・ダイクストラの変形の仕方が間違ってる。

  • priority queueを使ったダイクストラでは、次のノードへのエッジをキューに入れていく。
  • ただし、同じノードへ到達できるより小さなコストのエッジが見つかった場合、前に見つかったエッジを破棄し、新たなエッジをキューに入れる。
  • この破棄の際に、これまでに数えた親の数もリセットして1に戻さないといけない。これが抜けていた・・・

→んー・・・単純な間違いがないことは一通り確認したが、この辺まで深く考えてなかった。。

→ダイクストラなどは元々複雑なことをやっているので、変形には細心の注意を払わなければ・・・


それにしても、DPをあきらめてグラフ最短路のアプローチへ移行するのが遅すぎました。

視野を広げてさまざまなアプローチを試すというところはできてきましたが、よりBFS的に早めに切り替えていかなければいけないかな。。


以下、修正したソースです。

typedef long long ll;

vector <int> val, mul;
vector <int> dad;
const ll unseen=2000000000;
vector <vector <int> > wgt;
int gs;
const int MOD=1000000007;

class TreesCount {
public:
	void visit_a(int k) {//ダイクストラ
		int m;
		priority_queue <pair <int, int> > pq;
		pair <int, int> qt;

		val[k]=0; dad[k]=k;
		qt.first=0; qt.second=k;
		pq.push(qt);
		while(!pq.empty()) {
			qt=pq.top(); pq.pop();
			m=qt.second;
			if(val[m]<-qt.first) continue;
			for(int i=0; i<(int)wgt[m].size(); i++) {
				if(m==i) continue;
				if(!wgt[m][i]) continue;
				if(val[i]==val[m]+wgt[m][i]) mul[i]++;//同じコストで到達した場合、親の数をインクリメント(提出時にダイクストラに追加したのはこの文だけ)
				if(val[i]>val[m]+wgt[m][i]) {
					val[i]=val[m]+wgt[m][i]; dad[i]=m;
					mul[i]=1;//親の数を1に初期化(この文が抜けていた)
					qt.first=-val[i]; qt.second=i;
					pq.push(qt);
				}
			}
		}
	}

	int count(vector <string> graph) {
		ll res=1;

		//グラフの初期化
		gs=graph.size();
		mul.assign(gs, 1);
		dad.assign(gs, -1);
		val.assign(gs, unseen);
		wgt.assign(gs, vector <int>(gs));

		for(int i=0; i<gs; i++) for(int j=0; j<gs; j++) wgt[i][j]=graph[i][j]-'0';

		//ダイクストラによる最短路探索
		visit_a(0);

		//各ノードの親の数を掛けあわせ
		for(int i=0; i<gs; i++) {
			res=(res*mul[i])%MOD;
		}
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20100701