AT_ddcc2019_final_a レース (Race)

[problemUrl]: https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_a 高橋君はペンギンのレース場を作りました。 レース場は $ N $ 個の正方形のマスが西から東に一列に並んだ形状をしています。 これらのマスの状態は文字列 $ S $ により表され、西から $ i $ 番目のマスの状態は $ S $ の $ i $ 文字目が `-` なら「雪」、`>` なら「氷」です。 また、スタート地点は西端のマスの西の端、ゴール地点は東端のマスの東の端です。 高橋くんのペンギンが、スタート地点からゴール地点を目指して東に進みます。 ペンギンは、雪マスを $ 1 $ マス通過するのに $ 1 $ 秒、氷マスを $ 1 $ マス通過するのに $ 1/(k+2) $ 秒の時間を要します。 ここで、$ k $ はその氷マスの直前に連続して存在する氷マスの個数です。 例えば、雪マスの直後に氷マスが $ 2 $ つ存在する場合、$ 1 $ つ目の氷マスは $ 1/2 $ 秒、$ 2 $ つ目の氷マスは $ 1/3 $ 秒で通過します。 ペンギンがスタートする前に、高橋君は雪マスのうち $ 1 $ つを氷マスに変えることができます。 ペンギンがスタート地点を出発してからゴール地点に到達するまでに最小で何秒かかるでしょうか？

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S $

ペンギンがゴール地点に到達するのに要する秒数の最小値を出力せよ。 ジャッジの出力との相対誤差または絶対誤差が $ 10^{-8} $ 以下であれば正解となる。

### 制約 - $ 3\ \leq\ N\ \leq\ 100\ 000 $ - $ S $ は `-`, `>` で構成される長さ $ N $ の文字列 - $ S_1\ =\ S_2\ =\ S_{N-1}\ =\ S_N\ = $ `-` - **$ S $ において、`-` は必ず別の `-` と隣接して現れる** ### Sample Explanation 1 西から $ 4 $ 番目のマスを雪マスから氷マスに変えると、レース場は `-->>-` となります。 このとき、ペンギンは西から $ 1,\ 2,\ 3,\ 4,\ 5 $ 番目のマスの通過にそれぞれ $ 1,\ 1,\ 1/2,\ 1/3,\ 1 $ 秒、合計で $ 23/6\ =\ 3.83333333... $ 秒を要し、これが最短です。 ### Sample Explanation 2 どのマスを雪マスから氷マスに変えても、ペンギンは $ 13/2\ =\ 6.5 $ 秒でゴールします。 ### Sample Explanation 3 西から $ 2 $ 番目または $ 6 $ 番目のマスを雪マスから氷マスに変えると、ペンギンは $ 407/60\ =\ 6.783333333... $ 秒でゴールすることができます。