レース (Race) [DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦 A]

https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_a

解説

https://atcoder.jp/contests/ddcc2019-final/submissions/4044638

「Sにおいて、- は必ず別の - と隣接して現れる」という奇妙な条件があるので、ここから考える。
この条件は「>->」となっている部分がないということを示している。
最適な方針を考えると、「なるべく氷を連続させる」という方針がある。
「>->」で途中をつなげて「>>>」とすることで伸ばす方法もあるが、これは条件で排除されているので、
既存の氷群を伸ばすことで最適な答えを得る。
ここで伸ばすべきは最も長さが長いものを更に伸ばすべきである。
　
さて、ここまでわかればあとは実装。
自分はランレングス表現にして、処理した。
runLengthEncoding関数でその処理を行っている。

vector<pair<char, int>> runLengthEncoding(string s) {
    int n = s.length();
 
    vector<pair<char, int>> res;
    char pre = s[0];
    int cnt = 1;
    rep(i, 1, n) {
        if (pre != s[i]) {
            res.push_back({ pre, cnt });
            pre = s[i];
            cnt = 1;
        }
        else cnt++;
    }
 
    res.push_back({ pre, cnt });
    return res;
}

　
ランレングスにしたら、'>'で個数が最大のものを探してそれを伸ばして、隣の'-'を1つ減らせばいい。
文字列の先頭と末尾は'-'であるとされているので、隣は必ずある。
もし氷群がなかった場合は、末尾を氷群に変えればいい。
　
あとは、run部分でシミュレーションして、答え。

int N; string S;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;
 
    auto v = runLengthEncoding(S);
 
    // change
    int n = v.size();
    int ma = -1, id;
    rep(i, 0, n) if(v[i].first == '>' and ma < v[i].second) {
        ma = v[i].second;
        id = i;
    }
 
    if (ma < 0) {
        v[0].second--;
        v.push_back({ '>', 1 });
    } else {
        v[id].second++;
        v[id + 1].second--;
    }
 
    // run
    double ans = 0;
    fore(p, v) {
        if (p.first == '-') ans += p.second;
        else {
            rep(k, 0, p.second) ans += 1.0 / (k + 2);
        }
    }
    printf("%.10f\n", ans);
}