Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-04-20SRM468 Div1

SRM468 Div1 250 T9

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

Problem Statement

非常に問題文が長く、読むだけで10分以上かかりました。

アルゴリズムとして難しいところはないので、実装するだけです。

特にひっかけなどもなさそうなので、submit。

システムテストも問題なく通りました。

何人か落ちてる人がいましたが、あまり落ちるような要素は見つけられていなかったので、チャレンジはしていません。

source

SRM468 Div1 500 RoadOrFlightHard

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

Problem Statement

読んだ感じ、一瞬グラフかなと思いましたが、逆戻りするエッジがないので、DPで解けそうだなという印象を受けました。

しかし、街iまでフライトj回で到達できる最小時間を記録するDPをすると、40万*40で1600万のlong longのメモリが必要です。SRMで使えるメモリは64MBなので、long longに換算すると800万個程度までしか変数を使えません。このようにメモリ容量をオーバーする場合、コンパイルエラーにはならず、実行時にSIGKILLとかいうエラーが返るので、TLE狙いと同様チャレンジに使えます。

ということで、20分くらいダイクストラとか状態の持ち方を変えるとか色々考えてましたが、どれも計算量・メモリ量ともに大きすぎて、いい方法が思いつきません。

しかし、最初から気になっていたのですが、街iから街i+jにフライトする時間が、街iから街i+1へのフライト時間+・・・+街i+j-1から街i+jへのフライト時間となっており、最初に考えたようにDPした場合にこの条件を全然活かせないので、無駄があるのではないかと考えていました。

よく考えると、街iから街jへの経路は考える必要はないのでは・・?街iへの到達が歩いてきたかフライトしてきたかさえ記憶すれば、街i+1へフライトする際に、フライト回数を増やす必要があるかどうかは常に判定可能じゃないですか!!ということは、40万の街の状態をすべて覚えておく必要はなく、直前の街に到達したときの最小時間さえ覚えておけばよいことになるので、必要なメモリ量は2*40*2=160程度しかありません。

ということに気づいたときには、既に残り15分でした。ぎりぎり間に合うかと頑張りましたが、コンパイルエラーやら何やらで結局間に合わず。。。今回初めて知りましたが、大きな配列を宣言するときに、初期化するとエラーになることがあるんですね(こんな感じ→int rt[400010]={0})。"Your compiled binary exceeds the current system limit of 1000000 bytes"という不親切なエラーメッセージで全然原因が分からなくて非常に疲れました。宣言時に初期化するとバイナリコードにデータが埋め込まれるということなのかな。よくわかりませんが。

チャレンジタイムでは明らかにメモリ容量オーバーのコードを書いている人がいたので、ありがたく50点頂戴しました。

以下、本番終了後にバグを取った500点問題のsourceです。


typedef long long ll;
ll dp[2][42][2];
const ll INF=1000000000000000000LL;

class RoadOrFlightHard {
public:
	long long minTime(int N, int roadFirst, int roadProd, int roadAdd, int roadMod, int flightFirst, int flightProd, int flightAdd, int flightMod, int K) {
		long long result=0;
		int rt[400010], ft[400010];

		for(int i=0; i<1; i++) {
			for(int j=0; j<42; j++) {
				for(int k=0; k<2; k++) {
					dp[i][j][k]=INF;
				}
			}
		}

		rt[0]=roadFirst%roadMod; ft[0]=flightFirst%flightMod;
		for(int i=1; i<(int)N; i++) {
			rt[i]=((ll)rt[i-1]*roadProd+roadAdd)%roadMod;
			ft[i]=((ll)ft[i-1]*flightProd+flightAdd)%flightMod;
		}

		dp[0][0][0]=0;
		for(int i=1; i<=N; i++) {
			for(int j=0; j<=K; j++) {
				dp[i%2][j][0]=INF; dp[i%2][j][1]=INF;
			}
			for(int j=0; j<=K; j++) {
				//直前の街へは歩いてきて、次の街も歩いていく場合
				dp[i%2][j][0]=min(dp[i%2][j][0], dp[(i-1)%2][j][0]+rt[i-1]);
				//直前の街へはフライトで来て、次の街は歩いていく場合
				dp[i%2][j][0]=min(dp[i%2][j][0], dp[(i-1)%2][j][1]+rt[i-1]);
				//直前の街へはフライトで来て、次の街もフライトで行く場合
				dp[i%2][j][1]=min(dp[i%2][j][1], dp[(i-1)%2][j][1]+ft[i-1]);
				//直前の街へは歩いてきて、次の街はフライトで行く場合
				if(j<K) {
					dp[i%2][j+1][1]=min(dp[i%2][j+1][1], dp[(i-1)%2][j][0]+ft[i-1]);
				}
			}
		}
		result=INF;
		for(int i=0; i<=K; i++) {
			result=min(result, dp[N%2][i][0]);
			result=min(result, dp[N%2][i][1]);
		}

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