解法

いままで出力した文字数を y とします（初期値は 0）。下記のように、順にシミュレートしていきながら y を更新します。

英小文字を読んだときに x == y+1 となったらその文字を出力して終了です。数字を読んだときに x <= (d+1) * y となったら、x を x % y or y（a or b は、a が 0 なら b、そうでなければ a）で置き換えてシミュレーションを最初からやり直します。

上記の条件を満たさなければ、英小文字なら y += 1、数字 d なら y += d * y で更新します。

計算量解析

x = x % y で更新されるときは x が半分以下になります（有名事実）。 x = y で更新されるときは、x % y == 0（更新の条件）かつ x > y（シミュレーション中のループ不変条件）から、x >= 2 * y なので、やっぱり半分以下になります。

シミュレーションをやり直すたびに x が半分以下になることから、計算量は \(O(N\log(X))\) です。

実装

Python での例を挙げてみます。

def main():
    s = input()
    x = int(input())

    while True:
        y = 0
        for c in s:
            if c.islower():
                if x == y+1:
                    print(c)
                    return
                y += 1
            else:  # c.isdigit()
                d = int(c)
                if x <= (d+1) * y:
                    x = x % y or y
                    break
                y += d * y

main()

えびちゃんの日記

えびちゃん（競プロ）の日記です。

PAST #5 J - 長い長い文字列

解法

計算量解析

実装