結果

問題 No.3244 Range Multiple of 8 Query
コンテスト
ユーザー LyricalMaestro
提出日時 2026-01-05 21:53:42
言語 PyPy3
(7.3.17)
結果
WA  
実行時間 -
コード長 2,500 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 345 ms
コンパイル使用メモリ 82,392 KB
実行使用メモリ 166,072 KB
最終ジャッジ日時 2026-01-05 21:54:06
合計ジャッジ時間 21,398 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 13 WA * 10 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# https://yukicoder.me/problems/no/3244


def get_last_three_values():
    array = []
    for i in range(1000):
        if i % 8 == 0:
            i0 = 1000 + i
            str_i = str(i0)
            is_ok = True
            for s in str_i[-3:]:
                if s == "0":
                    is_ok = False

            if is_ok:
                array.append(str_i[-3:])
    return array

def solve_length1(s):
    if int(s) == 8:
        print(0)
    else:
        print(-1)

def solve_length2(s):
    # ひっくり返さない場合
    if int(s) % 8 == 0:
        print(0)
    else:
        s1 = s[1] + s[0]
        if int(s1) % 8 == 0:
            print(1)
        else:
            print(-1)


def solve_length3(seg_tree_list, s_list, last_three_values, l, r):

    answer = float("inf")
    for ideal_value in last_three_values:
        ans = 0

        target_index = r
        used_index = set()
        is_ok = True
        for ideal_digit in reversed(ideal_value):
            ind = seg_tree_list[int(ideal_digit)][target_index]
            while l < ind and ind in used_index:
                    ind = seg_tree_list[int(ideal_digit)][ind - 1]

            if ind < l:
                is_ok = False
                break

            w = 0
            for i in used_index:
                if ind <= i <= target_index:
                    w += 1
            ans += target_index - ind - w
            used_index.add(ind)
        if is_ok:
            answer = min(answer, ans)
    
    if answer == float("inf"):
        print(-1)
    else:
        print(answer)



def main():
    N, Q = map(int, input().split())
    S = input()
    lr = []
    for _ in range(Q):
        l, r = map(int, input().split())
        lr.append((l - 1, r - 1))

    # 3桁以上の場合、下３桁が以下のようになっていればOK
    last_three_values = get_last_three_values()

    s_list = [s for s in S]
    seg_tree_list = []
    for d in range(10):
        last_i = -1
        array = [-1] * N
        for i in range(N):
            if S[i] == str(d):
                last_i = i
            array[i] = last_i
        seg_tree_list.append(array)
 
    for l, r in lr:
        if r - l == 0:
            # 長さ1
            solve_length1(S[l])
        elif r - l == 1:
            # 長さ2
            solve_length2(S[l:(r + 1)])
        else:
            # 長さ3以上
            solve_length3(seg_tree_list, s_list, last_three_values, l, r)







if __name__ == "__main__":
    main()
0