2017-06-28

Codeforces #421 (Div. 1) B: Mister B and PR Shifts

まず初期状態のdeviationを計算しておく。

1回のcyclic shiftでdeviationの値がどのように変化するかを知りたい。

基本的には

p[i] < iのときp[i]の位置はiに近づくので、そのような値はdeviationを1だけ減らす。

p[i]>=iのときp[i]の位置はiから離れるので、そのような値はdeviationを1だけ増やす。

f:id:parukii:20170628125215j:plain

なので、次のcyclic shiftによってdeviationを減らす値と増やす値を数えておく。仮にそれぞれx, yとする。それによって毎ターンdeviationを増減させる。

ただし、この方針では右端が例外になる。

f:id:parukii:20170628130012j:plain

i(i>1)番目にある値はn-i回目のシフトで右端から左端へ移動する。このときだけ、deviationの計算をうまく分ける。

すなわち値zについて考える場合

deviationから|n-z|を引いて|1-z|を足す。また、このときx, yが変わる場合があるので注意。上図では

3は3から離れる => 3は3に近づく

というふうに状態が変化している。すなわち、

x++, y--

となる。

x, yの変化はもう1種類あって

f:id:parukii:20170628130807j:plain

のようにp[i]=iになるような場合で

x--, y++となる。

ただし、

f:id:parukii:20170628131331j:plain

のような場合に注意。

コード

Submission #28107263 - Codeforces

2017-06-27

SRM 716 DIV1 450: JumpDistancesOnTree

まず与えられた木の全点対の距離を計算しておく。

これを

d[u][v]: (u, v)間の距離

としておく。

d[u][v] ∈ Sかつu!=v であるような辺(u, v)をすべて持つようなグラフをHとする。このグラフでスタート地点の頂点0から探索して到達可能な頂点の集合をVとする。H上でv∈Vに到達できるということは、与えられた木の上での移動距離d[i]がすべてSに属することと同じ。ただし、Sの元うちどれを使っていて、どれを使っていないかは不明。ここで頂点w∈Vを

d[w][v] = Sの最大値

であるような頂点vが存在するような頂点とする。

もしそのような頂点が存在するならば、Sの元をすべて使うことができる。逆に、そうでなければ駄目なのは自明。

S[i]<S[i+1]

が成り立つのであった。

よってS[i+1]の移動ができると仮定すると、その移動とは逆方向にS[i]だけ移動することができる。したがってSの最大値の移動ができるならば、Sに属する距離になるようなすべての移動ができる。

2017-06-27

SRM 716 DIV1 250: ConstructLCS

ab<=bc<=caを仮定すると下の図のように解を構成できる。

f:id:parukii:20170627115456j:plain

実際はab, bc, caの大小関係はこのとおりとは限らない。なので、ソートしてから3個の文字列を作ってみる。あとはこの3個の文字列がa, b, cのどれに対応するかを全部試して、実際にLCSを計算してみればいい。

2017-06-21

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;
    }
}