AOJ 2541: Magical Bridges

magical bridgeの数はたかだか100個しかないので、使うmagical bridgeの数も100個以下である。

di[v][a]: magical bridgeをa回使ったときのSiからvの最短距離。ただし、magical bridgeの距離は0

とする。

ダイクストラ法によりd1とd2を事前に計算しておく。

xをmagical bridgeの距離とする。xは0以上の整数を自由にとる。

仮に、xを固定したとして考えてみる。このとき、

S1からTの最短距離は min[0<=a<101](a*x + d1[T][a])

S2からTの最短距離は min[0<=a<101](a*x + d2[T][a])

である。

要するにそれぞれの直線の集合から最小値を計算している。

そしてその差を最小にしたいのだった。

もしもxが非負の実数であったならば、最短距離の差を最小にするようなxの候補は、すべての直線のペアの交点の座標のいずれかである。しかし、交点は非負の整数でなければならないので、もし交点座標xが整数でなければ、xの代わりにfloor(x)とceil(x)を見る。

この解法に1つ例外があって、すべての直線のペアに交点がない場合である。このとき最適なxの値は任意。

// dis, pos, magical
using P = tuple<ll, int, int>;
const int X = 101;
const ll INF = (ll)1e12;
int N, M, S1, S2, T;
ll d1[1001][X], d2[1001][X];
// to, weight
vector<pii> G[1001];

void dijk(int S, ll d[1001][X]) {
    rep(i, N)rep(j, X)d[i][j] = INF;
    priority_queue<P, vector<P>, greater<P> > Q;
    Q.push(P(0, S, 0));
    while (sz(Q)) {
        ll di;
        int u, x;
        tie(di, u, x) = Q.top();
        Q.pop();
        if (d[u][x] < di)continue;
        d[u][x] = di;
        if (u == T)continue;
        each(e, G[u]) {
            ll ndi = di;
            int v, w, y = x;
            tie(v, w) = e;
            if (w != -1) {
                ndi += w;
            } else {
                y++;
            }
            if (y<X && d[v][y] > ndi) {
                Q.push(P(ndi, v, y));
            }
        }
    }
}

vll points(ll c1[1001][X], ll c2[1001][X]) {
    vll res;
    rep(a1, X)rep(a2, X)if (a1 != a2){
        ll b1 = c1[T][a1], b2 = c2[T][a2];
        ll den = a1 - a2;
        ll num = b2 - b1;
        if (num%den) {
            res.push_back(num / den + 1);
        }
        res.push_back(num / den);
        while (sz(res) && res.back() < 0)res.pop_back();
    }
    return res;
}

using L = pair<ll, ll>;
vector<L> lines(ll d[1001][X]) {
    vector<L> res;
    rep(i, X)if (d[T][i] != INF) {
        res.emplace_back(i, d[T][i]);
    }
    return res;
}

ll calcMin(vector<L> &ls, ll x) {
    ll res = LLONG_MAX;
    each(l, ls) {
        smin(res, l.first*x + l.second);
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (cin >> N >> M >> S1 >> S2 >> T, N) {
        --S1; --S2; --T;
        rep(i, N)G[i].clear();
        rep(i, M) {
            int u, v;
            string a;
            cin >> u >> v >> a;
            --u; --v;
            int w = a != "x" ? stoi(a) : -1;
            G[u].emplace_back(v, w);
            G[v].emplace_back(u, w);
        }
        dijk(S1, d1);
        dijk(S2, d2);
        
        vll xs = { 1 }, p11, p12, p22;
        p11 = points(d1, d1);
        p12 = points(d1, d2);
        p22 = points(d2, d2);
        xs.insert(xs.end(), all(p11));
        xs.insert(xs.end(), all(p12));
        xs.insert(xs.end(), all(p22));
        sort(all(xs));
        xs.erase(unique(all(xs)), end(xs));

        auto l1 = lines(d1), l2 = lines(d2);

        ll ans = LLONG_MAX;
        each(x, xs) {
            ll m1 = calcMin(l1, x), m2 = calcMin(l2, x);
            smin(ans, abs(m1 - m2));
        }
        cout << ans << endl;
    }
}
広告を非表示にする

Triplet Min Sum | CS Academy #30 (Div. 2 only)

実は解候補はlca(A,B), lca(B,C), lca(C, A)の3通りしかない。

与えられた木を根付き木とし、簡単のため

depth(A) <= depth(B) <= depth(C)

とする。Aを考慮しなければ、下のような図が描ける。

f:id:parukii:20170525205604j:plain

(1)Aがパス(B,C)上にある場合

明らかにAが解になる。

A=lca(A,B)またはA=lca(A,C)

(2)Aがパス(B,C)上にない場合

Aは上図の囲われていない部分のいずれかにある。Aパス(B,C)上にないので、Aからパス(B,C)に到達するのに必ず通らなければならないある(B,C)上のある1点が存在する。この点は

lca(A,B)またはlca(B,C)またはlca(C,A)

である。

 

 

Prefix Free Subset | CS Academy #30 (Div. 2 only)

f:id:parukii:20170525203320j:plain

文字列a,ab,abc,abdが与えられているとする。上図のようなtrieを描いてみよう。

簡単のため、文字列の最大の長さは考えないでみる。

K=1とすると明らかにaだけを使えばいい。

では、K=2の場合は?

K=1のときと同じようにaを使おうとすると、うまくいかない。aの子孫にあたる単語はすべてaをprefixとして含むため使えない。つまり、ab,abc,abdはすべて使えない。よってaは使わない。下図。

f:id:parukii:20170525203440j:plain

 

今度はabを使おうとすると、同様にabc,abdを使えない。これもK=2に届かない。

こうしてtrieを根から見ていくと、最終的に{abc, abd}を得る。

結局、自分を含まない先祖にあたるprefixを使ってない場合、ある単語について2通りの選択がある。

(1)その単語を使う

この場合はその子孫にあたる、その単語をprefixとして含む単語は使えない

(2)その単語を使わない

この場合はその子孫に当たる、その単語をprefixとして含む単語を使える。

(1),(2)を再帰でうまく処理する。最も長い単語の長さを二分探索で固定すれば、全体で

O(max(|S[i]|)*Σ|S[j]|)

の実行時間で間に合う。

 

 雑記

trieを使うのすぐに気付けなかった。ライブラリは持っておくべき。ちなみに、trieのことをprefix treeとも呼ぶらしく、解法を連想しやすいかも。 

Constant Sum | CS Academy #30 (Div. 2 only)

更新の操作は以下のように表せる。

A[i]+=s

A[j]+=-s/(N-1), j!=i

前者を変形すれば

A[i]+= (s+s/(N-1)) -s/(N-1)

となる。なので

全体に-s/(N-1)を加算し、A[i]にs+s/(N-1)を加算したとすれば、1クエリO(1)で処理できる。

 

Educational Codeforces Round 21 D: Array Division

f:id:parukii:20170517024850j:plain

n=1のとき明らかにNO
よってn>=2とする。
とりあえず、挿入は考えずに配列を前の部分(S)と後の部分(T)に分けてみる。ただし、S,Tは空であってもよいとする。
z=Σ[x∈S](x), w=Σ[y∈T](y)とする。
場合1. z=wの場合
ある要素を選んで同じ場所に挿入すればいいからYES
場合2. z>wの場合

Sから値vを取り除いてTに挿入したときに和が等しくなればYES
すなわち
z-v = w+vより
v = (z-w)/2としてv∈SならばYES
場合3. w>zの場合
場合2.と同様

S,Tはすべて試す。つまり、全ての前の部分の長さ(後ろの部分の長さ)を総当りで固定して、上記のチェックをすればいい。

Educational Codeforces Round 21 E: Selling Souvenirs

エディトリアル見て書いたコード。コメントつき

/*
エディトリアルのとおりの解法
*/
/*
重さ1, 2のsouvenirだけを使ったとき、重さの和がiとする。
このときdp[i]=(x,y,z)は以下の意味。
xはコストの和の最大値
yは重さ1のsouvenirをいくつ使ったか。
zは重さ2のsouvenirをいくつ使ったか。

インデックスのほうにy,zのような情報を持たせないで、最適値の後ろにくっつけてる。
*/
tuple<ll, int, int> dp[300001];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, M;
    cin >> N >> M;

    vll weight(N), cost(N);
    rep(i, N) {
        cin >> weight[i] >> cost[i];
    }

    // 重さの種類は3種類しかないのでバケツソートしておく。
    vll costByWeight[4];
    rep(i, N)costByWeight[weight[i]].push_back(cost[i]);
    // とりあえず、コストの大きい方から使いたいのでソートしておく。
    rep(i, 4)sort(costByWeight[i].rbegin(), costByWeight[i].rend());

    FOR(i, 1, M + 1)dp[i] = mt(-1ll, -1, -1);

    rep(i, M) {
        ll sumCost;
        int cnt1, cnt2;
        tie(sumCost, cnt1, cnt2) = dp[i];
        if (sumCost == -1)continue;
        if (cnt1 < sz(costByWeight[1])) {
            smax(dp[i + 1], mt(sumCost + costByWeight[1][cnt1], cnt1 + 1, cnt2));
        }
        if (cnt2 < sz(costByWeight[2]) && i + 2 <= M) {
            smax(dp[i + 2], mt(sumCost + costByWeight[2][cnt2], cnt1, cnt2 + 1));
        }
    }

    /*
    maxCost[i]は1,2の重さのsouvenirだけ使ったとき、重さの和がi以下である場合のコストの最大値
    */
    vector<ll> maxCost(M + 1);
    rep(i, M) {
        maxCost[i + 1] = max(maxCost[i], get<0>(dp[i + 1]));
    }

    // sumThreeは重さ3のsouvenirのコストの和
    ll answer = 0, sumThree = 0;
    // 重さ3のsouvenirのコストを総当りで固定する
    for (int i = 0; i <= M && i / 3 <= sz(costByWeight[3]); i += 3) {
        // 事前に計算したDPをうまく使って、解を更新する
        smax(answer, sumThree + maxCost[M - i]);
        if (i / 3 < sz(costByWeight[3])) {
            sumThree += costByWeight[3][i / 3];
        }
    }
    cout << answer << endl;
}

Educational Codeforces #21 G: Anthem of Berland

f:id:parukii:20170517004146j:plain

上図は3番目の入力例の文字列t="abcab"にダミーの1文字を加えたt+'#'="abcab#"に対してKMP法のDFAを描いたもの。!はその他の文字を表す。
tはオーバーラップしてもよいので、最終状態からの遷移もほしい。そこで、末尾にダミーの文字を加えた。これにより、最終状態からの遷移も得られた。
例えば
abcabと最後まで一致した後、
cが来た場合
接頭辞abcと一致するはず。実際、上図でそのような遷移が得られる。
|s|*|t|<=10^7という特殊な制約に注意しよう。
これにより、KMP法の計算以外ではO(|s|*|t|)の実行時間が許されている。
dp[i][j]を「Sの文字列をi番目まで確定していてDFA上で状態がjであるときの、DFA上のダミーでない最終状態に到達した回数の最大値」
とすれば、max(dp[|s|][j])が解。