典型90【076 – Cake Cut（★3）】をpython解説

AtCoder の問題を解くために必要な実力を付けるために作られた「典型問題」を解いていく企画として、「典型90」があります。

今回は、その内、の76問目である「 Cake Cut（★3）」を解説していきたいと思います。
なにか、間違っているところなどありましたら、@EitaSugiまで、ご指導ご鞭撻の程、よろしくお願い致します！

問題名　【076 – Cake Cut（★3）】

問題

問題概要

N個のピースに分かれた円形のホールケーキがあり、各ピースの大きさが与えられます。このケーキから、連続するピースを選んで、その部分がケーキ全体の大きさのちょうど10分の1になるかどうかを判定する問題です。

考察

循環する数列は2倍して考える

円形のケーキは循環しているので、配列を2倍にして直線的に考えることで、問題をシンプルにすることができます。

しゃくとり法

連続する区間の合計値を求める際に、しゃくとり法を利用します。この方法では、2つのポインタ \(L\) と \(R\) を使って、\(L,R\) の範囲の合計値 sum_LRを効率的に求めることができます。

• sum_LR<K の場合、 R を1つ進めて範囲を広げます。
• ssum_LR>K の場合、 L を1つ進めて範囲を狭めます。

この方法により、\(O(2N)\) で探索することが可能になります。

典型解法：しゃくとり法

コード

N = int(input())
A = list(map(int, input().split()))
A2 = A * 2  # 配列を2倍に
total = sum(A)
K = total // 10  # 全体の大きさの10分の1

if total % 10 != 0:  # もし10で割り切れないなら、解は存在しない
    print("No")
    exit()
else:
    left, x = 0, 0
    for right in range(2*N):  # 2*Nまで探索する
        x += A2[right]  # rightを1つ進めるたびにxに加える
        while x > K:  # xがKを超えた場合、leftを進める
            x -= A2[left]
            left += 1
        if x == K:  # xがKと等しいならYesを出力
            print("Yes")
            exit()

print("No")

まとめ

前の問題【075 – Magic For Balls（★3）】
次の問題【】