Problem p02775 (python)

Fixed submission:
import sys
read = sys.stdin.readline


# 下の桁から貪欲に見ていくと解ける
# 1の位が4以下ならそのまま紙幣で支払うのが得→自身をそのまま答えに採用 (枚数として加算)
# 6以上ならばお釣り狙いのほうが得→自身は0にセットして、上位桁を+1する (枚数として10-自身を加算)
# 5ちょうどのときは、お釣りもそのまま払っても枚数は変わらない。だけど555みたいに、上位桁に+1すると得になる可能性がある。
# 555→15枚, 1000-445→15枚
# つまり5が出たときは更に上位の桁を見て、4以下ならそのまま払うほうが得,5以上なら桁上りのほうが得

# 5ちょうどのときは？ #お釣りもそのまま払っても同じ。だけど上位 お釣り狙いだと上の桁が多くなって支払う金額が増える可能性がある？
# 5ピッタリのときに上位桁に+1すると悪くなる場合が存在する 455 とは 15にってしまう
# 5ピッタリのときはどうするのがよいのか？

N = '00' + read()[:-1]

N = N[::-1]
ans = 0
# agari = 0
# is_pre5 = False
# for n in N:
#     n = int(n) + agari
#     print(n, ans)
#     if is_pre5:
#         if n == 5:
#             ans += n
#             continue

#         if n < 5:
#             # そのまま支払う
#             ans += n
#             agari = 0
#         else:
#             # 桁上り
#             ans += 9 - n
#             agari = 1
#     else:
#         if n == 5:
#             is_pre5 = True
#             ans += n
#             agari = 0
#             # もし5だったら5が終わるまでなめる
#         elif n < 5:
#             ans += n
#             agari = 0
#         else:
#             ans += 10 - n
#             agari = 1
#     if n != 5:
#         is_pre5 = False

i = 0
lo = int(N[i])
while i < len(N) - 1:
    hi = int(N[i + 1])
    # print(hi, lo, i)
    if lo == 5 and hi == 5:
        # 5が連続してた場合
        # 5の最後まで移動(移動の道中は 5+4+4...としていく)
        # 5じゃなくなったhiに対して足し算する必要がある。
        ans += 5
        i += 1
        while i < len(N) - 1 and N[i + 1] == '5':
            ans += 4
            # print(i)
            i += 1
        ans += 4
        # low = N[i]
        hi = int(N[i + 1]) + 1
        # print(hi, lo, i)

        # loが5以外のとき (お釣りが良いか、そのまま払うのが良いか考えるだけ)
    elif lo == 5:
        ans += lo
        if hi < 5:
            pass
        else:
            hi += 1
    elif lo < 5:  # 5が連続しないときもここに入る
        ans += lo
    else:
        ans += 10 - lo
        hi += 1  # 上の桁が繰り上がる
    lo = hi  # 桁を一つずらす
    i += 1


print(ans)

Buggy submission (verdict: Runtime Error):
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


from functools import lru_cache
import sys
sys.setrecursionlimit(1 << 25)

N = read()[:-1]
siharai = ''


@lru_cache(None)
def F(n: str):
    '''
    支払う金額を返す。再帰関数
    '''
    global siharai
    # 終了条件
    if len(n) < 10 and int(n) < 5:
        siharai += str(n)
        return 0

    # 桁dpもどき
    # 1の位が4以下ならそのまま紙幣で支払うのが得→自身をそのまま答えに採用
    # 6以上ならばお釣り狙いのほうが得→自身は0にセットして、上位桁を+1する
    # 5ちょうどのときは？ #お釣りもそのまま払っても同じ。だけど上位 お釣り狙いだと上の桁が多くなって支払う金額が増える可能性がある？
    # 5ピッタリのときに上位桁に+1すると悪くなる場合が存在する 455 とは 15にってしまう
    # 5ピッタリのときはどうするのがよいのか？
    q, r = n[:-1], n[-1]
    if r == '5':
        qq, rr = q[:-1], q[-1]
        if int(rr) < 5:
            # そのまま
            joint = '5'
            F(q)
        else:
            joint = '0'
            F(str(int(q) + 1))
    elif int(r) < 5:
        joint = r
        F(q)
    else:
        joint = '0'
        F(str(int(q) + 1))
    siharai += joint


F(N)
siharai = int(siharai)
oturi = siharai - int(N)

ans = 0
for a in str(siharai) + str(oturi):
    ans += int(a)

print(ans)

Buggy submission (verdict: Runtime Error):
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


from functools import lru_cache
import sys
sys.setrecursionlimit(1 << 25)

N = read()[:-1]
siharai = ''


@lru_cache(None)
def F(n: str):
    '''
    支払う金額を返す。再帰関数
    '''
    global siharai
    # 終了条件
    if len(n) < 10 and int(n) < 5:
        siharai += str(n)
        return 0

    # 桁dpもどき
    # 1の位が4以下ならそのまま紙幣で支払うのが得→自身をそのまま答えに採用
    # 6以上ならばお釣り狙いのほうが得→自身は0にセットして、上位桁を+1する
    # 5ちょうどのときは？ #お釣りもそのまま払っても同じ。だけど上位 お釣り狙いだと上の桁が多くなって支払う金額が増える可能性がある？
    # 5ピッタリのときに上位桁に+1すると悪くなる場合が存在する 455 とは 15にってしまう
    # 5ピッタリのときはどうするのがよいのか？
    q, r = n[:-1], n[-1]
    if r == '5':
        qq, rr = q[:-1], q[-1]
        if int(rr) < 5:
            # そのまま
            joint = '5'
            F(q)
        else:
            joint = '0'
            F(str(int(q) + 1))
    elif int(r) < 5:
        joint = r
        F(q)
    else:
        joint = '0'
        F(str(int(q) + 1))
    siharai += joint


F(N)
siharai = int(siharai)
oturi = siharai - int(N)

ans = 0
for a in str(siharai) + str(oturi):
    ans += int(a)

print(ans)