Problem:


スコーン配達計画

愛歌さんの家は、小さな喫茶店を経営しています。愛歌さんのお母さんが焼くスコーンはとても美味しくて、店はとても繁盛していました。

ウェイトレスである愛歌さんの仕事の一つは、次々と焼き上がるスコーンを、お客様の席まで届けることです。焼きあがったスコーンはお盆の上に乗せられ、カウンターの上に一列に並べられます。i 番目のお盆の上に乗っているスコーンの数を Ki としましょう。愛歌さんは、それぞれのお客様にちょうど m 個のスコーンを運ばなければなりません。愛歌さんは一度にいくつでもお盆を持つことができ、また複数のお盆から 1 人のお客様にスコーンを配ったり、１つのお盆から複数のお客様に配っても構いません。

喫茶店にはとてもたくさんのお客様がやってくるので、カウンターに置いてある全てのスコーンを運んでも、全てのお客様に届けることはできません。しかし、できるだけ多くのお客様に届けた後で、m 個に満たない数のスコーンが余ることもあるかもしれません。そのようなスコーンは、お手伝いのご褒美として、愛歌さんが貰えることになりました。

ここでふと、愛歌さんは考えました。一度に全てのお盆を持つのではなく、一部のお盆だけを持ってお客様にスコーンを届けると、余るスコーンの数も違ってくるはずです。適切にお盆を選ぶことで、より多くのスコーンが余るようにできるかもしれません。愛歌さんは、作為的にお盆を選んでいることをお母さんに見抜かれないように、カウンターの上の1つの連続した範囲のお盆を選ぶことにしました。また、残ったお盆はお父さんやお母さんが運んでしまうので、愛歌さんがスコーンをもらうチャンスは一度しかありません。

さて、愛歌さんは最大いくつのスコーンを貰えるでしょうか？計算するプログラムを書いてください。お盆の数 n は 1 以上 30,000以下、 m は 1 以上 100,000 以下です。また数列の各要素 Ki は 0 以上 232-1 です。

入力

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。各データセットは以下のとおりです。

1行目 n m（整数 整数；半角空白区切り）

2行目 お盆上のスコーンの情報 K1 K2 ...  Kn（すべて整数 ; 半角空白区切り）

Ki: i番目のお盆上のスコーンの数

データセットの数は 50 を超えません。

出力

データセットごとに、もらえるスコーンの最大数を１行に出力します。

入力例

5 11
11 27 34 45 56
8 5
0 2 1 5 4 6 8 3
5 2
2 4 2 4 6
10 18
10 15 12 31 12 50 11 23 43 181
1 100
5
0 0

出力例

8
4
0
17
5



Sample input:
5 11
11 27 34 45 56
8 5
0 2 1 5 4 6 8 3
5 2
2 4 2 4 6
10 18
10 15 12 31 12 50 11 23 43 181
1 100
5
0 0


Sample output:
8
4
0
17
5

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl

while True:
  n, m = map(int, input().split())
  if n == 0:
    break
  klst = list(map(int, input().split()))
  cum = []
  acc = 0
  for k in klst:
    acc += k
    acc %= m
    cum.append(acc)
  
  use = [0]
  use_len = 1
  ans = 0
  for k in cum:
    ind = bl(use, m - k - 1)
    if ind < use_len:
      if use[ind] == m - k - 1:
        ans = max(ans, k + use[ind])
      else:
        ans = max(ans, k + use[ind - 1])
    ans = max(ans, (k + use[-1]) % m)
    use.insert(bl(use, k), k)
    use_len += 1
  print(ans)

Submission status: Accepted

Solution code:
# AOJ 0254: Scone
# Python3 2018.6.25 bal4u

s = [0 for i in range(30001)]
while True:
	n, m = map(int, input().split())
	if n == 0: break
	f = [-1 for i in range(m)]
	sum, nmax, ans = 0, 0, 0
	a = list(map(int, input().split()))
	for i in range(n):
		sum += a[i]
		a[i] %= m
		if a[i] > nmax: nmax = a[i]
		if a[i] == m-1: ans = a[i]
		s[i+1] = s[i] + a[i]
		if s[i+1] >= m: s[i+1] -= m
		f[s[i+1]] = i+1
	if ans == 0:
		if nmax == 0: ans = 0
		elif sum < m: ans = sum
		else:
			done = False
			for ans in range(m-1, nmax-1, -1):
				for i in range(n+1):
					x = s[i]+ans
					if x >= m: x -= m
					if f[x] >= i:
						done = True
						break
				if done: break
	print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl

while True:
  n, m = map(int, input().split())
  if n == 0:
    break
  klst = list(map(int, input().split()))
  cum = []
  acc = 0
  for k in klst:
    acc += k
    acc %= m
    cum.append(acc)
  
  use = [0]
  use_len = 1
  ans = 0
  for k in cum:
    ind = bl(use, k + 1)
    if ind < use_len:
      ans = max(ans, (k - use[ind]) % m)
    ans = max(ans, k)
    use.insert(bl(use, k), k)
    use_len += 1
  print(ans)

Submission status: Accepted

Solution code:
def main():
    while 1:
        N, M = map(int, input().split())
        if N == M == 0:
            break
        data = [0]*(M+1)
        def add(k, x):
            while k <= M:
                data[k] += x
                k += k & -k
        def get(k):
            s = 0
            while k:
                s += data[k]
                k -= k & -k
            return s
        M0 = 2**(M-1).bit_length()
        def lower_bound(x):
            w = i = 0
            k = M0
            while k:
                if i+k <= M and w + data[i+k] <= x:
                    w += data[i+k]
                    i += k
                k >>= 1
            return i+1
        *K, = map(int, input().split())
        su = 0
        ans = 0
        for k in K:
            su = (su + k) % M
            v = get(su+1)
            w = lower_bound(v)-1
            if w == M:
                w = 0
            ans = max(ans, (su - w) % M)
            add(su+1, 1)
        print(ans)
main()