Download presentation
Presentation is loading. Please wait.
1
問題：The hik Revolutions 解説：田村（sune2）
Problem D TiMe Table 問題：The hik Revolutions 解説：田村（sune2）
2
問題 S個のバス停がある区間をM本のバスが通る バス停の位置とN人の利用者がどのバス停にいつ来る かの情報が与えられる
1≦S, N, M ≦ 2000
3
考察 i番目の利用者を待ち時間0で拾うために営業所を出な ければならない時間はすぐに計算できる この時間をTiとする
i番目の利用者を時刻Tに出発したバスで拾うとき，この 利用者の待ち時間はT-Tiとなる
4
DP 利用者をTiでソートする dp[i][d] = i番目までの利用者までをd番目のバスまで を使って回収した時の，待ち時間の和の最小
dp[i][d] = min_{0<=j<=i} {dp[j][d-1] + sum(i,j) } ここで sum(i,j) = Σ_{j+1<=k<=i} len(k,i) len(k,i) = Ti – Tk 答えはdp[N][M]
![DP 利用者をTiでソートする dp[i][d] = i番目までの利用者までをd番目のバスまで を使って回収した時の，待ち時間の和の最小](http://slidesplayer.net/slide/15731804/88/images/4/DP+%E5%88%A9%E7%94%A8%E8%80%85%E3%82%92Ti%E3%81%A7%E3%82%BD%E3%83%BC%E3%83%88%E3%81%99%E3%82%8B+dp%5Bi%5D%5Bd%5D+%3D+i%E7%95%AA%E7%9B%AE%E3%81%BE%E3%81%A7%E3%81%AE%E5%88%A9%E7%94%A8%E8%80%85%E3%81%BE%E3%81%A7%E3%82%92d%E7%95%AA%E7%9B%AE%E3%81%AE%E3%83%90%E3%82%B9%E3%81%BE%E3%81%A7+%E3%82%92%E4%BD%BF%E3%81%A3%E3%81%A6%E5%9B%9E%E5%8F%8E%E3%81%97%E3%81%9F%E6%99%82%E3%81%AE%EF%BC%8C%E5%BE%85%E3%81%A1%E6%99%82%E9%96%93%E3%81%AE%E5%92%8C%E3%81%AE%E6%9C%80%E5%B0%8F.jpg "dp[i][d] = min_{0<=j<=i} {dp[j][d-1] + sum(i,j) } ここで. sum(i,j) = Σ_{j+1<=k<=i} len(k,i) len(k,i) = Ti – Tk. 答えはdp[N][M]")
5
DP O(N^2 M)で遅い 高速化 一般にX(i,d) = min_{j<i} { X(j,d-1) + w(i,j) } 型のDP は，wがMongeなら O(NM) で計算可能 SWARK algorithmを用いる この問題では，monotone minimaを用いたO(NM log N)の解法でも通る
6
monotone minima dp[i][d] = min_{0<=j<=i} {dp[j][d-1] + sum(i,j) } dを固定して考える dpd[i] = min_{0<=j<=i} Ad-1[i][j] 行列Ad-1の各行において，minを高速に求めたい sumがMongeであることから，Ad-1もMongeとなり， argmin Ad-1[i][j]はiに対して単調増加することが知ら れている Ad-1
![monotone minima dp[i][d] = min_{0<=j<=i} {dp[j][d-1] + sum(i,j) } dを固定して考える. dpd[i] = min_{0<=j<=i} Ad-1[i][j]](http://slidesplayer.net/slide/15731804/88/images/6/monotone+minima+dp%5Bi%5D%5Bd%5D+%3D+min_%7B0%3C%3Dj%3C%3Di%7D+%7Bdp%5Bj%5D%5Bd-1%5D+%2B+sum%28i%2Cj%29+%7D+d%E3%82%92%E5%9B%BA%E5%AE%9A%E3%81%97%E3%81%A6%E8%80%83%E3%81%88%E3%82%8B.+dpd%5Bi%5D+%3D+min_%7B0%3C%3Dj%3C%3Di%7D+Ad-1%5Bi%5D%5Bj%5D.jpg "行列Ad-1の各行において，minを高速に求めたい. sumがMongeであることから，Ad-1もMongeとなり， argmin Ad-1[i][j]はiに対して単調増加することが知ら れている. Ad-1.")
7
monotone minima 分割統治により再帰的に各行のminを求める 真ん中の行を走査してminを見つける
調べる領域は必ず半分程度になる
8
monotone minima このようにしてminを求める処理を各dに対して順に行う O(NM log N) 参考
後で同じような問題が既出だったことを知りました
Similar presentations
