B - Evilator

Contest Duration: 2017-05-27(Sat) 12:00 - 2017-05-27(Sat) 13:50 (local time) (110 minutes) Back to Home

B - Evilator Editorial

Time Limit: 2 sec / Memory Limit: 256 MiB

配点 : $400$ 点

問題文

すけぬ君は、 $N$ 階建てのビルを建てました。ビルにはエレベーターが $1$ 基あり、すべての階に止まります。

すけぬ君は、各階に上下の方向ボタンを設置しましたが、うっかりしていたため、どの階にも上向きか下向きの片方のボタンしかありません。そのため、どの階からも上か下のどちらかにしか進むことができません。 $S_i$ が U のとき $i$ 階には上向きのボタンしかなく、上にしか進めないことを、D のとき下向きのボタンしかなく、下にしか進めないことを表します。

ある階から目的の階へと移動したい住民は、仕方がないので必要があれば他の階を経由して目的の階へと向かうことにしました。全ての階の順序対 $(i,j)$ についての、 $i$ 階から $j$ 階へ行くときのエレベーターに乗る回数の最小値の合計を求めてください。

制約

$2 ≦ |S| ≦ 10^5$
$S_i$ は U または D である
$S_1$ は U である
$S_{|S|}$ は D である

入力

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

 $S_1S_2...S_{|S|}$

出力

全ての階の順序対 $(i,j)$ についての、 $i$ 階から $j$ 階へ行くときのエレベーターに乗る回数の最小値の合計を出力せよ。

入力例 1Copy

Copy

UUD

出力例 1Copy

Copy

$1$ 階から $2$ 階までは、 $1$ 回エレベーターに乗れば行くことができます。

$1$ 階から $3$ 階までは、 $1$ 回エレベーターに乗れば行くことができます。

$2$ 階から $1$ 階までは、 $2$ 回エレベーターに乗れば行くことができます。

$2$ 階から $3$ 階までは、 $1$ 回エレベーターに乗れば行くことができます。

$3$ 階から $1$ 階までは、 $1$ 回エレベーターに乗れば行くことができます。

$3$ 階から $2$ 階までは、 $1$ 回エレベーターに乗れば行くことができます。

これらの合計は $7$ なので、 $7$ を出力します。

入力例 2Copy

Copy

UUDUUDUD

出力例 2Copy

Copy

Score : $400$ points

Problem Statement

Skenu constructed a building that has $N$ floors. The building has an elevator that stops at every floor.

There are buttons to control the elevator, but Skenu thoughtlessly installed only one button on each floor - up or down. This means that, from each floor, one can only go in one direction. If $S_i$ is U, only "up" button is installed on the $i$ -th floor and one can only go up; if $S_i$ is D, only "down" button is installed on the $i$ -th floor and one can only go down.

The residents have no choice but to go to their destination floors via other floors if necessary. Find the sum of the following numbers over all ordered pairs of two floors $(i,j)$ : the minimum number of times one needs to take the elevator to get to the $j$ -th floor from the $i$ -th floor.

Constraints

$2 ≤ |S| ≤ 10^5$
$S_i$ is either U or D.
$S_1$ is U.
$S_{|S|}$ is D.

Input

The input is given from Standard Input in the following format:

 $S_1S_2...S_{|S|}$

Output

Print the sum of the following numbers over all ordered pairs of two floors $(i,j)$ : the minimum number of times one needs to take the elevator to get to the $j$ -th floor from the $i$ -th floor.

Sample Input 1Copy

Copy

UUD

Sample Output 1Copy

Copy

From the $1$ -st floor, one can get to the $2$ -nd floor by taking the elevator once.

From the $1$ -st floor, one can get to the $3$ -rd floor by taking the elevator once.

From the $2$ -nd floor, one can get to the $1$ -st floor by taking the elevator twice.

From the $2$ -nd floor, one can get to the $3$ -rd floor by taking the elevator once.

From the $3$ -rd floor, one can get to the $1$ -st floor by taking the elevator once.

From the $3$ -rd floor, one can get to the $2$ -nd floor by taking the elevator once.

The sum of these numbers of times, $7$ , should be printed.

Sample Input 2Copy

Copy

UUDUUDUD

Sample Output 2Copy

Copy