ABC 237

Table of Contents

C - kasaka

https://atcoder.jp/contests/abc237/tasks/abc237_c

先頭にある連続する a の数を $x$, 末尾に連続する a の数を $y$ とすると $x > y$ のとき, どうやっても回文にはできない. それ以外のとき, 先頭と末尾の a を消して残った文字が回文になっていれば Yes, そうでなければ No.

初め以下のようなコードを書き AC を取れてしまったが, これは嘘解法.

void solve() {
    string s;
    cin >> s;
    int l = 0, r = (int)s.size() - 1;
    while (l < r) {
        // 頭に a を追加する
        if (s[l] != 'a' && s[r] == 'a') {
            r--;
        } else if (s[l] == s[r]) {
            l++;
            r--;
        } else {
            cout << "No" << endl;
            return;
        }
    }
    cout << "Yes" << endl;
    return;
}

axyaxa という文字列のとき上のプログラムだと Yes を出力するが, 本来は No を出力すべき

D - LR insertion

問題

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    deque<int> deq = {n};
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == 'R') {
            deq.push_front(i);
        } else {
            deq.push_back(i);
        }
    }
    rep(i, n + 1) {
        if (i == 0)
            cout << deq.at(i);
        else
            cout << ' ' << deq.at(i);
    }
    cout << endl;
}

愚直にやるならば双方向連結リストの要領で要素の挿入をいっていけば良い.

スマートにやるならば deque を使い $\{ N \}$ の状態から初めてクエリを逆順に処理していき, R ならば先頭に, L ならば末尾に要素を追加していくとよい.

E - Skiing

https://atcoder.jp/contests/abc237/tasks/abc237_e

解説 AC

負のコストの辺があっても負閉路がなければダイクストラでも一応最短経路を求めることができるが、巧妙にテストケースを作られると TLE してしまう。

ref: 普通にダイクストラをして TLE するケース

頂点 $i,j,k$ に対して $H_i < H_j > H_k$ とすると、$i \rightarrow j \rightarrow k$ と移動すると楽しさは

\begin{align*} \text{楽しさ} &= -2(H_j - H_i) + (H_j - H_k) \\ &= (H_i - H_k) - (H_j - H_i) \end{align*}

頂点 $i,j,k,l,m$ に対して $H_i < H_j > H_k < H_l > H_m$ とすると、$i \rightarrow j \rightarrow k \rightarrow l \rightarrow m$ と移動すると楽しさは

\begin{align*} \text{楽しさ} &= (H_i - H_k) - (H_j - H_i) - 2 (H_l - H_k) + (H_l - H_m) \\ &= (H_i - H_k) - (H_j - H_i) + (H_k - H_m) - (H_l - H_k) \\ &= (H_i - H_m) - \left\{ (H_j - H_i) + (H_l - H_k) \right\} \end{align*}

となる。これらより、頂点 $i$ から頂点 $j$ へ移動するときの楽しさは $( H_i - H_j ) - (\text{登った距離の総和})$ と表すことができる。 頂点 $i \rightarrow j$ から移動するとき $H_i \geq H_j$ のときはコスト $0$, $H_i < H_j$ のときはコスト $H_j - H_i$ で移動する最短経路問題を解くと「登った距離の総和」の最小値を求めることができる。 最終的に $\max_{i} \left\{ H_0 - H_i + (i \rightarrow j \text{の経路で登った距離の総和}) \right\}$ を求めれば良い。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    vll height(N);
    rep(i, N) cin >> height[i];
    vvll graph(N);
    rep(i, M) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    // cost, position
    using P = pair<ll, int>;
    priority_queue<P, vector<P>, greater<P>> pq;
    pq.push({0, 0});
    vll dist(N, INF);
    dist[0] = 0;
    while (pq.size()) {
        auto [cost, now] = pq.top();
        pq.pop();

        if (dist[now] < cost) continue;

        for (int nx : graph[now]) {
            ll hx = height[now], hy = height[nx];
            ll nxd = cost;
            if (hx < hy) nxd += hy - hx;
            if (dist[nx] <= nxd) continue;
            dist[nx] = nxd;
            pq.push({nxd, nx});
        }
    }

    ll ans = 0;
    rep(i, N) chmax(ans, height[0] - height[i] - dist[i]);
    cout << ans << endl;
}