kmjp's blog

競技プログラミング参加記です

UnKoder #05 : Marathon Record

その他コンテスト

良い問題でした。
https://www.hackerrank.com/contests/unkoder-05/challenges/marathon-record

問題

1～N番の選手がマラソンを行った。

各人のスタート・ゴール時刻について、時系列の記録がある。
ただし、記録の一部はかすれており、スタートかゴールかは判別できるものの誰がスタート・ゴールしたか不明な場所がある。

着順としてあり得る組み合わせ数を求めよ。

解法

今回求めるのは着順の組み合わせなので、ゴール者が不明な記録に遭遇するたび、そこに当てはまる適切な人の組み合わせをDPで数え上げることになる。

まず記録を1回見て、以下の人数を数え上げよう。

  • スタートもゴールも記録にある人
  • スタートだけ記録にある人
  • ゴールだけ記録にある人
  • どちらも記録にない人

以後のDPではdp[記録の行番号][スタート位置未確定の人数]=組み合わせ、として処理していく。

まず、どちらも記録にない人は互いの順番を入れ替え可能である。
よって以後「どちらも記録にない人」はすべて同一であるとして処理を行い、最初か最後にどちらも記録にない人の数の階乗を掛ければよい。

記録を以下の順で処理していく。
記録の人が確定しており、かつその人はスタートもゴールも記録があるなら、その人の記録は全体に何も影響しないので、dp[L][x]=dp[L-1][x]と状態をコピーするだけ。
以下は記録が不確定か、もしくは対象の人はスタートかゴールのどちらかが不明である場合を考える。

  • スタートの記録かつ対象の人が判明
    • スタート位置未確定の人は増えないので、dp[L][x]=dp[L-1][x]で状態をコピー。
  • スタートの記録かつ対象の人が不明
    • スタート位置未確定の人が1人増えるので、dp[L][x+1]=dp[L-1][x]。
  • ゴールの記録かつ対象の人が判明
    • ゴールの位置が確定している人は、逆にスタート位置は未確定だったはずである(両方確定している人は最初の除外されている)
    • よってスタート位置未確定の空き位置を1つ割り当てる必要があるので、dp[L][x-1]=dp[L-1][x]。
  • ゴールの記録かつ対象の人が不明
    • ここが一番重要なところ。スタート位置が確定の人のうち誰かか、もしくはスタート位置が未確定の人を対応付ける。
    • この時点でスタート位置未確定の人がx人の場合、逆にスタート位置確定(でまだゴール位置との対応付けが済んでない)の人はここまでの(スタート記録数)-(ゴール記録数)-xで計算できる。
    • よってスタート位置が確定の人のうち誰かを対応付ける場合、dp[L][x] += dp[L-1][x]*確定数。
    • よってスタート位置が未確定の人のうち誰かを対応付ける場合、dp[L][x-1] += dp[L-1][x]。
int N;
int D[5050];

string S[10100];
int ID[10100];
int numfr, nums,numg;
ll mo=1000000007;
ll dp[2][5011];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,2*N) {
		cin>>S[i]>>ID[i];
		if(ID[i]!=0) {
			if(S[i]=="S") D[ID[i]] |= 1;
			if(S[i]=="G") D[ID[i]] |= 2;
		}
	}
	
	dp[0][0]=1;
	FOR(i,N) if(D[i+1]==0) dp[0][0]=dp[0][0]*(++numfr)%mo;
	
	FOR(i,2*N) {
		int cur=i%2,tar=cur^1;
		if(D[ID[i]]==3) {
			memmove(dp[tar],dp[cur],sizeof(dp[cur]));
			continue;
		}
		ZERO(dp[tar]);
		if(S[i]=="S") {
			FOR(x,5001) dp[tar][x+(ID[i]==0)]+=dp[cur][x];
			nums++;
		}
		else {
			if(ID[i]==0) {
				FOR(x,5001) if(dp[cur][x]) {
					// take free
					if(x) (dp[tar][x-1] += dp[cur][x])%=mo;
					// take fix
					int fix = nums - numg - x;
					if(fix>0) (dp[tar][x] += fix * dp[cur][x])%=mo;
				}
			}
			else {
				FOR(x,5001) if(x) dp[tar][x-1]+=dp[cur][x];
			}
			numg++;
		}
	}
	
	cout<<dp[0][0]<<endl;
}

まとめ

最初スタートとゴール合わせて組み合わせ数を求めてしまった。