ABC 237

Table of Contents

C - kasaka

先頭にある連続する 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

問題

楽しさを最大化したいから楽しさの増減を辺のコストとすると最長経路問題となる. 最長経路問題はコストを $-1$ 倍して最短経路問題を解くと求まる. ダイクストラ法では負のコストを扱えず, ベルマンフォード法では計算量が $O(|V||E|)$ となるので 今回の問題だと TLE になる.