SRM 481 div1 hard: TicketPrinters

問題

解法

2 つ解法があるみたいですが, とりあえず DP 解で書きました。

topcoder の解説に他の解(最大マッチングに持ち込む)があったので, そっちにも少し触れます(書いてないので言ってることが正しいかわかりませんが)。

dp 解では, ある状態において, 既に訪れた printer が区間 [lp, rp] で表されることに注目します。

こうなっていないとすると, 例えば [0, 1] の printer は既に働いていて, 2 の printer は働いていなくて, [3, 6] の printer は働いている, という状態とかになるわけですが, どこからスタートしたとしても, この場合は printer[2] には一度訪れているわけで, そこで printer を動かさないのは明らかに損なので, 区間 [lp, rp] の printer は既に動かしていると考えて良いわけです。

また, 状態で区間 [lp, rp] がわかったとして, 今いる場所は, 左端(lp) か, 右端(rp) であることもわかります。

dp[lr][lp][rp][state] = (区間 [lp, rp] には到達済みで, printer に既に設定した数字の集合が state である時の, コストの最小値) とします。lr は, 今左端にいるか, 右端にいるかを表します。

このように dp を決めると, 今いる地点 cur が lp, rp, lr からわかり, cur でどの数字を印刷するか決めて, 左側に行くか右側に行くかの遷移しかないので, O(n) で各状態は計算できます。

ただ, 配列を上のように取ると MLE で死んでしまうので, dp[lr][lp][state] にします。lp と state に立っている bit の数 cnt がわかれば, rp = lp+cnt と決まるので, rp はなくても大丈夫なんですね。

次に, 最大マッチングに帰着する解法です。

上と同じような考察で, 各 printer への動き方は, 「今まで調べた区間の左側に行くか, 右側に行くか」しかないことがわかります。このような動き方は, 多く見積もって 2^16 程度しかありません。実際には, combination(16, 8) 程度らしいです。まず, この printer への動き方を全探索します。

で, あとは二分探索です。ある値 x 以内にすべての数を印刷しきれるかどうかを考えます。全探索して, 各 printer にどれだけの時間でたどり着けるかがわかっていますが, その場合分けのそれぞれについて, 各 printer にどの数字を割り当てるかを決めると, すべての printer について, 最終的にどれだけの時間をかけて印刷が完了するかがわかります。

そこで, printer[i] にたどり着くまでの時間 + そこから数字 num[j] を印刷するまでのコスト cost[i][j] が x 以下ならば, i -> j に辺を貼ります。
このようにして出来たグラフについて, 最大マッチングを取った時, マッチング数が n に等しくなるなら, x 以内にすべての数を印刷できることになります。

const int INF = 1e9;
int n;
int dp[2][16][1<<16]; // leftOrRight, rightPos, state
int dist[16][16];
vi startValue, wantedValue;

// [lp, rp]
// lr=0: lp, lr=1: rp
int dfs(int lr, int lp, int rp, int state) {
    int& ret = dp[lr][lp][state];
    if (ret >= 0) return ret;
    int cur = (lr==0) ? lp : rp;
    ret = INF;
    for (int i = 0; i < n; i++) if ((state>>i&1)==0) {
        int tmp = INF;
        if (lp > 0) {
            tmp = min(tmp, dist[cur][lp-1] + dfs(0, lp-1, rp, state|(1<<i)));
        }
        if (rp < n-1) {
            tmp = min(tmp, dist[cur][rp+1] + dfs(1, lp, rp+1, state|(1<<i)));
        }
        int cost = abs(startValue[cur]-wantedValue[i]) + 1;
        if (tmp == INF) tmp = cost;
        else tmp = max(tmp, cost);
        ret = min(ret, tmp);
    }
    return ret;
}

class TicketPrinters {
public:
    int minTime(int currentPrinter, vector <int> printerDistance, vector <int> startingValues, vector <int> wantedValues) {
        startValue = startingValues;
        wantedValue = wantedValues;
        n = startValue.size();
        for (int i = 0; i < n; i++) {
            memset(dist[i], 0, sizeof(dist[i]));
            for (int j = i+1; j < n; j++) {
                dist[i][j] = dist[i][j-1]+printerDistance[j-1];
            }
        }
        for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) {
            dist[i][j] = dist[j][i];
        }
        memset(dp, -1, sizeof(dp));
        int ans = dfs(0, currentPrinter, currentPrinter, 0);
        return ans;
    }
};

mayoko’s diary

プロコンとかいろいろ。

SRM 481 div1 hard: TicketPrinters

問題

解法