ベスパリブ

プログラミングを主とした日記・備忘録です。ベスパ持ってないです。

ABC032: C問題の解説 (Python3)

問題:AtCoder Beginner Contest 032: C - 列

公式解説:https://www.slideshare.net/chokudai/abc032

しゃくとり法の問題です。

公式解説を読むと、「連続する1を圧縮する」という重要なテクニックが書かれていますが、本記事ではそうではない方法で解いています。解法としては少し変わったしゃくとり法です。

しゃくとり法といえば区間の和を効率よく求める方法ですが、今回の問題は区間の積のしゃくとり法といった感じです。

解説

 K = 6
 4 3 1 1 2 2 1 1 1 2

という数列について考えます。

# 初期状態
 4 3 1 1 2 2 1 1 1 2
|_|
 4

# 右端の位置を1すすめる
 4 3 1 1 2 2 1 1 1 2
|___|
  12

# K=6を超えたので、左端の4で割ったあと、左端の位置を1すすめる
 4 3 1 1 2 2 1 1 1 2
  |_|
   3

# 右端の位置を1すすめるという操作を繰り返す(累積がK=6を超えるまで操作を繰り返す)
 4 3 1 1 2 2 1 1 1 2
  |_______|
      6

# 右端の位置を1すすめる
 4 3 1 1 2 2 1 1 1 2
  |_________|
       12

# K=6を超えたので、左端の3で割ったあと、左端の位置を1すすめる
 4 3 1 1 2 2 1 1 1 2
    |_______|
         4

# 右端の位置を1すすめるという操作を繰り返す(累積がK=6を超えるまで操作を繰り返す)...(※)
 4 3 1 1 2 2 1 1 1 2
    |_____________|
          4

# 右端の位置を1すすめる
 4 3 1 1 2 2 1 1 1 2
    |_______________|
           8

# K=6を超えたので、左端の1で割ったあと、左端の位置を1すすめる
 4 3 1 1 2 2 1 1 1 2
      |_____________|
             8

# まだK=6を超えてるので、左端の1で割ったあと、左端の位置を1すすめる
 4 3 1 1 2 2 1 1 1 2
        |___________|
             8

# まだK=6を超えてるので、左端の2で割ったあと、左端の位置を1すすめる
 4 3 1 1 2 2 1 1 1 2
          |_________|
               4

# 右端の位置を1すすめるが、これ以上すすめれないので終了
 4 3 1 1 2 2 1 1 1 2
          |_________|
               4

よって答えは、(※)のときの7

上記例の入力は以下になります。

10 6
4
3
1
1
2
2
1
1
1
2

コーナーケース

  • 数列に0が登場したら、全数列の積は必ず0になるので、Nを出力すれば良い。
  • K=0のとき、
    • 数列に0が登場するなら、全数列の積は0になり、これはK以下の制約を満たす。よってNを出力する
    • 数列に0が登場しないなら、どの部分列の積も必ず1以上になるので、これはK以下の制約を満たせない。よって0を出力する

実装

# -*- coding:utf-8 -*-
import sys


def solve():
    N, K = list(map(int, sys.stdin.readline().split()))
    Ss = []
    for _ in range(N):
        s = int(input())
        Ss.append(s)

    if K == 0:
        # コーナーケース
        if 0 in Ss:
            print(N)
        else:
            print(0)
        return

    left = 0   # 左端
    ans = 0    # 最終的に出力する答え
    accum = 1  # 累積
    for right in range(N):
        accum *= Ss[right]

        if accum == 0:
            # 0を掛けた場合は例外で、Nを出力して終了
            print(N)
            return

        while accum > K:
            accum //= Ss[left]
            left += 1
        ans = max(ans, right-left+1)
    
    print(ans)


if __name__ == "__main__":
    solve()

計算量は、たとえば K=10、数列が 1 1 1 1 1 1 1 1 1 1 1 99 みたいな最悪ケースを考えると、そのときはwhile accume > K: の合計操作回数がNになるので、最悪計算量が  O(2N) = O(N) だと思います。たぶん。

あるいは、rightは高々N回右に移動するし、leftも高々N回右に移動するので、やっぱり  O(2N) = O(N) だと思います。

while accum > K: のwhileループで左端の位置を右に1だけ移動させる操作を繰り返していますが、実はこの問題の性質上、ループさせなくてもただ1回だけ操作をするだけで良さそうです(そうやって解いてる人もいた)。