ABC258E - Packing Potatoes

方法1

考え方

• 各じゃがいもの種類$i$に対して，$i$スタートで重さの総和が$X$以上になるときの「個数」と「その次の箱に入るじゃがいもの種類$j$」を求めることができる．
• 上の結果から$i\to j$に辺を張った有向グラフを考えると，周期$N$以下でループする．

上記2つによって，

1. $K$番目の箱の先頭のじゃがいもを求め，
2. 「先頭のじゃがいも→個数」のテーブルを参照する

ことで解ける．

やりたいことはわかるが，バグらせないようにするのが大変．．．

Editorial - AtCoder Beginner Contest 258

回答例

バグるポイントが多すぎて，あまり良くない実装かも．

from collections import deque

N, Q, X = map(int, input().split())
W = list(map(int, input().split()))
W2 = deque(W + W)
tot = sum(W)

G = []
num_i_start = [N * (X // tot)] * N
X %= tot
tot_now, cnt = 0, 0
now = deque()
for i in range(N):
    while tot_now < X:
        w = W2.popleft()
        now.append(w)
        tot_now += w
        cnt += 1
    num_i_start[i] += cnt
    G.append((i + cnt) % N)
    if not now:continue  # X == 0
    w = now.popleft()
    tot_now -= w
    cnt -= 1

seen = [False] * N
cur = 0
seen[0] = True
path = [0]
cnt = 1
ord = {0:cnt}
for _ in range(N):
    chi = G[cur]
    if seen[chi]:
        loop_start = ord[chi]
        break
    seen[chi] = True
    path.append(chi)
    cnt += 1
    ord[chi] = cnt
    cur = chi

period = len(path) - loop_start + 1
for _ in range(Q):
    K = int(input())
    if K < loop_start:
        print(num_i_start[path[K - 1]])
    else:
        num = loop_start + (K - loop_start) % period
        print(num_i_start[path[num - 1]])