AGC-015-B Evilator

■■■問題■■■

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

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

SiがUのときi階には上向きのボタンしかなく、上にしか進めないことを、
Dのとき下向きのボタンしかなく、下にしか進めないことを表します。

ある階から目的の階へと移動したい住民は、
仕方がないので必要があれば他の階を経由して目的の階へと向かうことにしました。

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

■■■入力■■■

S1S2 ・・・ S|S|

●2 <= |S| <= 10万
●SiはUまたはDである
●S1はUである
●S|S| はDである

■■■出力■■■

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

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("UUD");
            //7
            //1階から2階までは、1回エレベーターに乗れば行くことができます。
            //1階から3階までは、1回エレベーターに乗れば行くことができます。
            //2階から1階までは、2回エレベーターに乗れば行くことができます。
            //2階から3階までは、1回エレベーターに乗れば行くことができます。
            //3階から1階までは、1回エレベーターに乗れば行くことができます。
            //3階から2階までは、1回エレベーターに乗れば行くことができます。
            //これらの合計は7なので、7を出力します。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("UUDUUDUD");
            //77
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string S = InputList[0];

        long Answer = 0;
        for (int I = 0; I <= S.Length - 1; I++) {
            long ShitaCnt = I;
            long UeCnt = S.Length - ShitaCnt - 1;

            if (S[I] == 'U') {
                Answer += ShitaCnt * 2;
                Answer += UeCnt;
            }
            if (S[I] == 'D') {
                Answer += ShitaCnt;
                Answer += UeCnt * 2;
            }
        }
        Console.WriteLine(Answer);
    }
}

解説

1階からは、上に進めて
最上階からは、下に進めるので、
どの階からであっても、高々2回エレベーターに乗れば任意の階に行けます。

後は、全ての順序対での
エレベーターに乗る回数を合計してます。