結果

問題 No.78 クジ付きアイスバー
ユーザー norioc
提出日時 2025-05-14 00:24:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 43 ms / 5,000 ms
コード長 1,485 bytes
コンパイル時間 368 ms
コンパイル使用メモリ 82,788 KB
実行使用メモリ 60,176 KB
最終ジャッジ日時 2025-05-14 00:24:33
合計ジャッジ時間 3,330 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

def floyds_cycle_finding(a0, f) -> tuple[int, int]:
    """
    フロイドの循環検出法
    a0 : 初期値
    f  : 次の値を求める関数
    return: tuple[サイクルに入るまでの長さ, サイクルの長さ]
    """
    x = y = a0
    while 1:
        x = f(x)
        y = f(f(y))
        if x == y:
            break

    x = a0
    head_len = 0
    while x != y:
        x = f(x)
        y = f(y)
        head_len += 1

    cycle_len = 0
    while 1:
        x = f(x)
        y = f(f(y))
        cycle_len += 1
        if x == y:
            break

    return head_len, cycle_len


def simulate(k, stock):
    buy = 0
    s = stock
    for i in range(k):
        if s > 0:
            s -= 1
        else:
            buy += 1

        s += ds[i % N]

    return buy, s


def box(stock):
    s = stock
    for i in range(N):
        if s > 0:
            s -= 1
        s += ds[i]

    return min(s, 100)


INF = 1 << 60
N, K = map(int, input().split())
S = input()
ds = [int(c) for c in S]

if K < 1000:
    buy, stock = simulate(K, 0)
    print(buy)
    exit()

head_len, cycle_len = floyds_cycle_finding(0, box)
buy, stock = simulate(head_len * N, 0)
# print(f'{head_len=} {cycle_len=}')

k = K - (head_len * N)
tot_b = 0
s = stock
for _ in range(cycle_len):
    b2, s = simulate(N, s)
    tot_b += b2
# assert s == stock, (s, stock)

t = max(0, k // (cycle_len * N) - 10)

buy += tot_b * t
rest = k - (t * N)
b2, s = simulate(rest, s)
buy += b2

print(buy)
0