AGC015 B - Evilator

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time
import numpy as np
from numpy import linalg as LA

# 時々使う
# import numpy as np
# from decimal import Decimal, ROUND_HALF_UP
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


# MOD = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    S = iss()
    N = len(S)

    ret = 0
    for i in range(N):
        if S[i] == 'U':
            ret += i*2 + N-i-1
        else:
            ret += i + (N-i-1) * 2
    print(ret)


if __name__ == '__main__':
    main()

考え方

移動方法は2種類しか存在しません。
全ての階には必ず1度の移動または2度の移動で到達可能です。

---

どのような移動が考えられるか、
例として5階建てのビルの3階からの移動を考えます。

3階がU（昇りのエレベーター）である場合について考えます。
3階から上に移動することが可能なため、
4階と5階には1度の移動で到達可能です。
逆に1階と2階には、一度上った後に、
くだりのエレベーターに乗る必要があるため、2度移動が必要です。

3階がD（下りのエレベーター）である場合について考えます。
3階から下に移動可能なため、
1階と2階には1度の移動で到達可能です。
逆に4階と5階には、一度下がった後に、
昇りのエレベーターに乗る必要があるため、2度移動が必要です。

以上のことから、次のことが分かります。

• 全ての階層には1度の移動または2度の移動で到達可能
• ある階のエレベーターが昇りの場合には、上の階には1度の移動・下の階には2度の移動で到達可能
• ある階のエレベーターが下りの場合には、上の階には2度の移動・下の階には1度の移動で到達可能

あとは全ての階において、上記の条件を元に計算を行うことで、
エレベーターに乗る最小回数の合計を求めることが出来ます。