問題: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になるので、最悪計算量が だと思います。たぶん。
あるいは、rightは高々N回右に移動するし、leftも高々N回右に移動するので、やっぱり だと思います。
while accum > K:
のwhileループで左端の位置を右に1だけ移動させる操作を繰り返していますが、実はこの問題の性質上、ループさせなくてもただ1回だけ操作をするだけで良さそうです(そうやって解いてる人もいた)。