ARC104 C. Fair Elevator
問題
下の階から1～2Nの番号がついた2N階の建物がある。
1階から2N階まで1度だけ動いて、その際、N人の人が乗り降りをした情報と、各階で乗り降りした人は1人のみであることがわかっている。
人iはA_iで乗りB_iで降りたことが記録されており、以下のような条件を満たしていた。
- 人iがエレベータに乗っているとき、他の人が乗り降りした回数をC_iとする
- 人iと人jが同時にエレベータに乗っていた瞬間が存在する場合は、C_i = C_jを満たす
ところで、記録(A_i, B_i)の一部は消えてしまっており、消えた情報は-1で表されている。
また、記録が誤っている可能性もある。
残っている記録に矛盾がないような乗降の組み合わせがあるか？
制約
- 1 <= N <= 100
- A_i, B_iは-1または1～2Nの整数
解法
まず、明らかに条件を満たさないケースを除く。
「各階で乗り降りが1人のみ」で、N人が2N階で乗り降りしたので、誰も乗り降りしなかった階はないことがわかる。
なので、A_i, B_iが-1ではないのに重複がある場合は、条件を満たせない。
また、A_i, B_iが-1でないときA_i > B_iもおかしいので、条件を満たせない。
以降、上記以外の場合を考える。
C_iの条件を考えると、偶数長の区間[l,r)において、m=(r-l)/2とすると、
・lからl+m
・l+1からl+m+1
・・・・
・l+m-1からl+2m-1
の対応関係になっていないといけない。(隙間なく順番に乗って降りている状況)
このような対応関係がいくつか組み合わさって全部の階について満たしているかを確認すれば良い。
区間dpで考えると、
dp[l][r] := 区間[l,r)で条件を満たすような対応関係があるか否か
とすると、メモ化再帰で、区間[l,r)についてdp[l][r]を求める関数をsolve(l, r)として、
・l～rの間の地点iを区切りに[l,i)と[i,r)の区間がそれぞれ対応関係がある場合はそれを連結して[l,r)でも対応関係がある、とできる
・上記がない場合、[l,r)で対応関係があるかを確認する
とできる。
「[l,r)で対応関係があるか」を考える。
上で書いたC_iの条件から対応関係が決まるので、そのようなものが実際に作れるかをチェックする。
x(=l～l+m-1)からy(=l+m～l+2m-1)という場合を考えると、
・xから乗ってきた人がいて、yで降りた人がいる場合
・同じ人でなければダメ
・xから乗ってきた人がいて、yで降りた人はわからない場合
・乗ってきた人の降りた階が-1でないとダメ
・xで乗ってきた人がわからなく、yで降りた人がいる場合
・降りた人の乗った階が-1でないとダメ
・xで乗ってきた人も、yで降りた人もわからない場合
・(特にダメな条件はなし。(-1,-1)の人を割り当てればよい)
でダメな条件がある場合は、ダメで、そうでなければ対応関係が作れる。
最終的にdp[0][2*N]が答えになる。
解法2
dp[i] := i階までで対応関係が作れるか？
で十分で、dp[j]がtrueなら、[j,i)の区間において対応関係が作れるかをチェックすればdp[i]が更新できる。
答えはdp[2*N]。
