Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-05-05SRM469 Div1

SRM469 Div1 250 TheMoviesLevelOneDivOne

| 12:29 | SRM469 Div1 250 TheMoviesLevelOneDivOne - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM469 Div1 250 TheMoviesLevelOneDivOne - SRM diary(Sigmar) SRM469 Div1 250 TheMoviesLevelOneDivOne - SRM diary(Sigmar) のブックマークコメント

Problem Statement

やるだけの問題です。予約済みの席がある列だけ数え上げをして、それ以外の列は(席数-1)×列数で計算すれば答えが出ます。

どうも書くのが遅くてバグ多いしでダメダメでした。もっと綺麗なコードで早く書けるようになりたいです。

結果はpassed system testです。

source

SRM469 Div1 500 TheMoviesLevelTwoDivOne

| 12:29 | SRM469 Div1 500 TheMoviesLevelTwoDivOne - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM469 Div1 500 TheMoviesLevelTwoDivOne - SRM diary(Sigmar) SRM469 Div1 500 TheMoviesLevelTwoDivOne - SRM diary(Sigmar) のブックマークコメント

Problem Statement

いかにもDPな感じの問題です。

見終えた映画の集合を状態として、起きたまま見れた映画の最大数を記憶するんだろうなという感じで進めましたが、問題で求められているのが、最大数ではなく見る順番なので、順番をどうやって記憶するかで引っかかってしまいました。

とりあえずvectorで見た順番を全部記憶してみると、MLEかつTLEにもなってしまうので、ダメです。いろいろ考えましたが結局時間内には分からず。

チャレンジタイムではvectorでDPしてる人が2人いたので何となくこの人たちはダメそうだなと思い突撃してみたところ1成功1失敗で+25になりました。

後で分かったのですが、順番については全て記憶する必要はなく、ある状態から次にどの映画を観ると見れる映画数が最大になるかだけを記憶しておけば、あとで最適な順番が計算できるので、vectorを使う必要はありませんでした。

分かってしまえば何てことはないですが、こういうちょっとしたブレイクスルーがDPの勘所というか、難しいところなんでしょうね・・・簡単なようで意外と分からないものです。

以下、終了後に書いたコードです。映画20本でも状態数2^20×平均更新数10=約1000万ループの計算量で、700msくらいで終わるのですが、このコードを最初書いたときは再帰関数recにlengthとscaryのvectorを引数で渡していたところ、TLEしてしまいました。これまたTLEする原因が分からず、修正に苦労しました。。引数にvectorを渡すと、vectorのコピーやらで時間がかかるのかな?引数でvectorを渡すのは注意が必要なようですね。。。


typedef long long ll;
int seen[1<<20]; //起きたまま見れた映画数
int nxt[1<<20]; //次にどの映画を見ると見れる映画数が最大になるか
int lens;
vector <int> len, sc;

class TheMoviesLevelTwoDivOne {
public:
	int rec(int s, int d) {
		int result, tmp;
		int li=-1, scsum=0;

		if(seen[s]>=0) return seen[s];

		if(d==lens) return d;
		result=0;

		//scare levelの現在値を計算
		scsum=74+47*d;
		for(int i=0; i<lens; i++) {
			if(s&(1<<i)) scsum-=len[i];
		}

		for(int i=0; i<lens; i++) {
			if(s&(1<<i)) continue;
			//眠らなかった場合のみ次の映画へ
			if(scsum>=sc[i] && scsum+47-len[i]>=0) tmp=rec(s^(1<<i), d+1);
			else tmp=d;
			if(tmp>result) {
				result=tmp;
				li=i;
			}
		}

		seen[s]=result;
		nxt[s]=li;
		return result;
	}

	vector <int> find(vector <int> length, vector <int> scary) {
		vector <int> result;
		bool used[20]={false};
		int s=0;

		lens=length.size();
		len=length; sc=scary;
		memset(seen, -1, sizeof(seen));
		memset(nxt, -1, sizeof(nxt));
		rec(s, 0);

		//起きたまま見れた映画の順番を計算
		for(int i=0; i<lens; i++) {
			if(nxt[s]<0) break;
			used[nxt[s]]=true;
			result.push_back(nxt[s]);
			s^=(1<<nxt[s]);
		}
		//眠ってしまった映画の順番を計算
		for(int i=0; i<lens; i++) {
			if(!used[i]) result.push_back(i);
		}

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