Codeforces Round #370

A Memory and Crow

問題

a_i = b_i - b_i+1 + b_i+2 - b_i+3.... で定義される数列a, bがある
数列aが与えられるので、数列bを求める

解法

後ろから計算して求めればOKなので、愚直にやったがO(n²)となりTLE
計算すると b_i = a_i - b_i+1 となるので、これを使えばO(n)となって間に合う

int main() {
    int n;
    cin >> n;
    vi a(n);
    REP(i, n) {
        cin >> a[i];
    }

    vi b(n, a[n - 1]);
    for (int i = n - 2; i >= 0; i--) {
        b[i] = a[i] + a[i+1];
    }

    REP(i, n) {
        cout << b[i];
        if (i != n - 1) {
            cout << " ";
        }
    }
    cout << endl;

    return 0;
}

B Memory and Trident

問題

上下左右への移動を表すU, D, L, Rからなる文字列が与えられる
移動が終わった後にスタート地点に戻れるように文字列を変更するとき、最小の変更箇所の数を求める
どう変更してもダメなときは-1を返す

解法

移動が奇数回のときはどう頑張ってもNG
一か所の変更で軌道修正が可能なのは以下の2パターン
- 上下または左右のずれ2つ分（U→D, L→R の書き換え）
- 上下のずれ1つ分と左右のずれ1つ分（U,D↔L,R の書き換え）
スタート地点からの上下のずれ＋スタート地点からの左右のずれを2で割ったものが答え

int main() {
    string s;
    cin >> s;

    int l = s.length();
    if (l % 2) {
        cout << -1 << endl;
        return 0;
    }

    int v = 0, h = 0;
    REP(i, l) {
        switch (s[i]) {
        case 'R':
            v++;
            break;
        case 'L':
            v--;
            break;
        case 'U':
            h++;
            break;
        case 'D':
            h--;
            break;
        default:
            break;
        }
    }

    cout << (abs(v)+abs(h))/2 << endl;
    
    return 0;
}

C Memory and De-Evolution

問題

一辺の長さがxの正三角形を、一辺の長さがyの正三角形に変換したい（x > y）
一回の操作で、三角形が成立する範囲で一辺の長さを自由に変えられる
最小の操作回数を求める

解法

問題文の通り貪欲に操作しようとすると、一辺が極端に短くなってしまい残りの二辺の操作に手間取るケースがあり、うまくいかない
問題分の逆の操作を貪欲にするとうまくいく（なぜかは不明）

int main() {
    int x, y;
    cin >> x >> y;

    if (x == y) {
        cout << 0 << endl;
        return 0;
    }

    vi l(3, y);

    int ans = 0;
    while (!(l[0] == x && l[1] == x && l[2] == x)) {
        int nl = l[1] + l[2] - 1;
        if (nl > x) {
            nl = x;
        }
        l[0] = nl;
        sort(ALL(l));
        
        ans++;
    }

    cout << ans << endl;

    return 0;
}

D Memory and Scores

問題文軽く読んで諦め（眠み）.

結果

oooxx (Unrated)

サーバーにつながりにくいなどがあり途中でUnratedのアナウンス. 発想回だっただけに残念.