【paiza問題集 解説】
paizaの森練習問題コンテスト過去問題セット9

n, k = map(int, input().split())
a = list(map(int, input().split()))

max_ = -float('inf')
for i in range(n-k + 1):
    max_ = max(max_, sum(a[i:i+k]))

print(max_)

ループで先頭から k 日間分をスライスで取得し、その総数を最大値と比較して更新していっています。

n, k = map(int, input().split())
a = list(map(int, input().split()))

sum_ = sum(a[:k-1])

max_ = -float('inf')
for i in range(n-k+1):
    sum_ += a[i+k-1]
    max_ = max(max_, sum_)

    sum_ -= a[i]

print(max_)

n, k = map(int, input().split())
a = list(map(int, input().split()))

cum_sum = [0]
for i in range(n):
    cum_sum.append(cum_sum[i] + a[i])

# これでも累積和が作れる
# c = 0
# cum_sum = [0] + [c:=c+i for i in a]

max_ = -float('inf')
for i in range(k, n+1):
    max_ = max(max_, cum_sum[i] - cum_sum[i-k])

print(max_)

例１はスライディングウィンドウ法と呼ばれるアルゴリズムを使って最大値を探索しています。

例２は累積和というアルゴリズムで最大値を探索しています。

n, k = map(int, input().split())
a = list(map(int, input().split()))

sum_ = sum(a[:k-1])

max_ = -float('inf')
for i in range(n-k+1):
    sum_ += a[i+k-1]
    max_ = max(max_, sum_)

    sum_ -= a[i]

print(max_)

k = 3
a = [3, 8, 4, 9, 1, 6, 7, 5]

まず先頭から k - 1 の 個数の要素を合計します。

sum_ = sum(a[:k-1])

[3, 8], 4, 9, 1, 6, 7, 5
sum_ = 3 + 8 = 11

次にループに入り、次の要素 4 を sum_ に足します。

for i in range(n-k+1):
    sum_ += a[i+k-1]

[3, 8, 4], 9, 1, 6, 7, 5
sum_ = 11 + 4 = 15

次に、値を比較して最大値を取ります。

max_ = max(max_, sum_)

先頭の要素の数を引きます。

sum_ -= a[i]

3, [8, 4], 9, 1, 6, 7, 5
sum_ = 15 - 3 = 12

次のループに移ります。

3, [8, 4, 9], 1, 6, 7, 5
sum_ = 12 + 9 = 21
max_ = max(15, 21)
max_ = 21
3, 8, [4, 9], 1, 6, 7, 5
sum_ = 21 - 8 = 13

表にして見てみましょう。

↓ max_ = 11

↓ max_ = 15

↓ max_ = 21

↓ max_ = 21

↓ max_ = 21

↓ max_ = 21

max_ = 21

　　　 の所をウィンドウ(窓)とみなし、それが左から右へとスライドしている様だからスライディングウィンドウです。常に 　　　 の枠に入った次の数を足し、漏れた数を引いています。画面がスクロールする時がこんな感じですね。

１つ前の「卵の最大の生産量」のプログラムでも強引にできないことはないのですが、1つ進む度に毎回総和を求めては無駄です。例えばウィンドウの範囲が 1000個の場合、毎回 999回足し算をして総和を求め、それを k と比較して、次にもまた 999回足し算をして……。💤
スライディングウィンドウ法は都度、新しい値を足して、不要となった値を引く２回の処理を繰り返すだけで済みます。

n, k = map(int, input().split())
a = list(map(int, input().split()))

cum_sum = [0]
for i in range(n):
    cum_sum.append(cum_sum[i] + a[i])

max_ = -float('inf')
for i in range(k, n+1):
    max_ = max(max_, cum_sum[i] - cum_sum[i-k])

print(max_)

k = 3
a = [3, 8, 4, 9, 1, 6, 7, 5]

まず、累積和を作ります。累積和については paiza問題集「定番アルゴリズム - 累積和メニュー」で学習できます。当サイトでもその問題集の解説を作ってありますので、よければ活用してください。😊

cum_sum = [0, 3, 11, 15, 24, 25, 31, 38, 43]

やっていることはスライディングウィンドウ法と同じようなものです。前処理が必要なものの、累積和はたった一回の引き算だけで区間和を求められます。累積和を作る時の足し算で１回、区間和を求める時の引き算で１回、計２回処理をするので理論上、計算量はスライディングウィンドウ法と差はありませんが。😅 でもこちらのほうがプログラムもシンプルなので混乱は少ないと思います。好みによりけりですが。

これも表にして見てみましょう。

↓ k の位置から始めます k = 3

↓ max_ = 15

↓ max_ = 21

↓ max_ = 21

↓ max_ = 21

↓ max_ = 21

max_ = 21

スライディングウィンドウ法にそっくりですが、累積和によってすでに値を足したものが用意されていますので、ループ中は引き算だけの処理になっています。足し算と引き算を同時に処理しているか分けて処理しているかの違いですね。

n, k = map(int, input().split())
a = list(map(int, input().split()))

cnt = 0
for i in range(1, 1 << n):
    egg = 0
    for j in range(n):
        if i & 1 << j:
            egg += a[j]
            if egg > k:
                break

    if egg == k:
        cnt += 1

print(cnt)

2 ^ n (2**n) は $2^n$、条件に「2 ≦ n ≦ 15」とありますので $2^{15}=$32768、何も選ばない選択はありませんので１を引いて、全 32767通りとなります。『選んだニワトリが産む卵の総和が k 個になる選び方は何通りあるか求めてください。』ということは、全 $2^n-1$、つまり最多で 32767通りの全てを調べなければいけません。

そこで今回はビット全探索というアルゴリズムを使って解きます。ビット全探索は、「paizaの森練習問題コンテスト過去問題セット3 - ラッキーナンバー」でも使いました。我ながらわかりやすい解説ができたとはとてもじゃないけど言えないのですが、その解説もあります。😓

その補足も兼ねて、今回も解説をしてみます。「ラッキーナンバー」の難易度はＢランクとなっていますが、めんどくささは同レベルです。今回Ａランクレベルの条件値となっていますが、ビット数が増えただけでアルゴリズム自体に変化はありません。入力 n の値(ビット数)を大きくしても変わらず処理してくれます。多分気付いてない。🤣

n = 8, k = 33
a = [3, 8, 4, 9, 1, 6, 7, 5]

要素数 8 で 8ビット。組み合わせ数は、全255通りです。00000001 〜 11111111 です。

a の要素番号 0 が ビットの１桁目、要素番号 1 が ２桁目………と対応します。そして、ビットが 1 になっている所に対応した a の数を全て足します。

if i & 1 << j:
    egg += a[j]

：
：

途中がっつり省略しましたが、この様に処理をしていきます。途中で k と同じ数、つまり卵がぴったりになる組み合わせを見つけたらカウントアップします。

この例では次の様な結果となりました。

５つ見つかりました。
▼ 試しにどうぞ！ ▼

1 << j は、ビットシフトです。00000001 を左に j だけずらします。

if i & 1 << j:
    egg += a[j]

　　　 の所は i & 1 << j の結果です。i がいくつの時でも 0、もしくはこの数値になります。この結果が 0 の時は Falseとなり、それ以外の時は True となって、egg に、a の 　 の数が加算されます。

    if egg > k:
        break

途中で egg の値が k を 超えてしまったら、それ以上加算しても k の値を下回るなんてことはありえませんので、さっさと break して次のループに移ってしまいましょう。😉

ポイントはやっばり、

if i & 1 << j:
    egg += a[j]

この部分でしょうか？ 特に i & 1 << j が理解できるようになったら、総てが理解できたも同然と言えるでしょう。

今ではグラフィック関連のソフトのカラービットに 16進数が当たり前のように使われるようになりました。ソフトの利用者もとても多くなり、16進数に馴染みがある方も多いかもしれませんが、その 16進数も元はといえば冗長な２進数を短く表現したものです。

16進数は１桁で４ビットです。２桁で８ビット = １バイトです。

光の三原色 (赤, 青, 緑) のとおり、昔のパソコンも RGB の三原色で表現されていました。

GRB
111 ← ３ビット

これ以外の色は存在しないので使えません。😅
七色の虹なんて言われてますけど、光ではない黒と、目に見えないとされる白を除いてこれを見ると、６色しかありませんね。単純な理論ですが、虹は基本６色ということが２進数によってわかります。

この後扱えるビット数が増え、16色が使え、256色が使え、4096色が使え、そして約1677万色が使える現在に至っています。

【２進数】
11111111(2) × 11111111(2) × 11111111(2) = 16,777,216(10)色
【16進数】
FF(16) × FF(16) × FF(16) = FFFFFF(16)色
※ 2進数、16進数は 0 も１色と数えます。

組み合わせは様々なシーンで使いますので、苦手意識を克服してサクサク使いこなせるようになりたいものです。← 私が