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