けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

2016 Benelux Algorithm Programming Contest D - Bridge Automation (AtCoder 600 点くらい)

バチャやりました!

vjudge.net

バチャの中では 4 問中 3 番目の難易度。問題の構造自体はこの記事の最後の章で書いたような典型的な区間分割型のナップサック DP なのですが、条件がゴチャゴチャしていてややこしかったです。。。

類題として、RUPC の以下の問題などがあります:

いわゆる

dp[ i ] = min_{0 <= j < i} (dp[ j ] + f(j, i) )

の形をした DP ですね。ナイーブにやると  O(n^{2}) ですが、

といった高速化テクニックが入りそうな形でもあります。

問題へのリンク

問題概要

ゲートに N 個の船が順にやって来る。船がやって来る間隔は 20 秒以上離れていることが保証される。以下の条件を満たしつつ、ゲートが開いている時間 (ゲートを開く間の時間や閉じる間の時間も含む) を最小化したい。

  • ゲートが完全に開いていないと船は通過することができない
  • ゲートが閉まっている状態から完全に開くまでに 60 秒かかる
  • ゲートが完全に開いている状態から閉まるまでに 60 秒かかる
  • 1 個の船がゲートを通過するのに 20 秒かかる
  • 2 個以上の船が同時にゲートを通過することはできない
  • 各船はゲートに到達してから、ゲートの通過を開始するまでの時間が 1800 秒以内でなければならない

制約

  • 1 <= N <= 4000
  • 60 <= T[i] <= 105 (各船が来る時刻)
  • T[i+1] - T[i] >= 20

解法

船が 1 個来るだけだったら、60 秒かけて開き、通過するのを 20 秒待ち、60 秒かけて閉じればいいので 140 秒である。

船が 2 個、かなりの時間の間隔を開けて来るなら、それが 2 倍で 280 秒である。しかし船が 2 個、近い間隔でやって来たならば、以下のような戦略がよい:

  • 船が 2 個とも到着するまでゲートは閉じておく
  • 2 個とも到着したら 60 秒かけてゲートを開ける
  • 2 個とも通過するのに 20 * 2 = 40 秒待つ
  • 60 秒かけてゲートを閉じる

こうして 160 秒で実現できる。

船が 3 台以上であっても同様なのだが、ここで注意が必要で、船は 1800 秒以上待つことはできない。なので、実際には

  • min(最初の船が到着してから 1800 秒後, 最後の船が到着する時刻) になってからゲートを開け始める
  • ゲートが開いたらすべての船が順に通過するのを待つ (船の到着時刻の間隔は 20 秒以上離れていることから、船の到着順に通過すれば大丈夫)
  • 60 秒かけてゲートを閉じる

さて、これは 1 回の開閉ですべての船を通す戦略である。実際には閉じたり開いたりする。「一緒に通過させる船たち」ごとにまとめていくと、これはまさに区間分割型のナップサック DP になっている。すなわち基本的には


dp[ i ] := 左から i 個までで一区切りつける場合のそこまでの最小値

dp[ i ] = min_{0 <= j < i}(dp[ j ] + f(j, i))


の形をした DP である。f(i, j) の計算を頑張ればよい。

#include <iostream>
#include <vector>
using namespace std;

int N;
vector<int> T;

int calc(int i, int j) {
    int left = T[i];
    int right = T[j-1];
    int num = j - i;
    int start = left + 1800 - 60;
    int owari = max(start+120+20*num, right+20+60);
    return owari - start;
}

int main() {
    cin >> N;
    T.resize(N);
    for (int i = 0; i < N; ++i) cin >> T[i];
    vector<int> dp(N+1, 1<<29);
    dp[0] = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = i+1; j <= N; ++j) {
            dp[j] = min(dp[j], dp[i] + calc(i, j));
        }
    }
    cout << dp[N] << endl;
}