0Pricing
Competitive Programming Academy · レッスン

固定サイズウィンドウの合計

長さ k のウィンドウを O(n) で移動します

「固定サイズウィンドウの合計」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。

繰り返し合計の問題

多くの問題では、k 個ずつ連続する要素の各ブロックの合計を求めます。各ブロックを毎回最初から計算し直すのは無駄が多いため、もっと効率よくできます。🪟

最初は遅い方法

素朴な方法では、長さ k の各ウィンドウを個別に合計します。これでは同じ処理を繰り返すため、計算量はO(n × k)となり、大きな入力には遅すぎます。

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

核心となる発想

隣り合うウィンドウは、ほとんど完全に重なっています。右に 1 つ移動すると、左端の要素を 1 つ取り除き、右側に新しい要素を 1 つ加えるだけです。

最初のウィンドウを初期化する

まず最初のk 個の要素を 1 回だけ合計します。この合計を基準として、ウィンドウを前にスライドさせながら更新していきます。

window = sum(a[:k])
best = window

1 ステップずつスライドする

ウィンドウを移動するには、入ってくる要素を加算し、出ていく要素を減算します。これにより、各ステップの処理を一定量の O(1) に保てます。

for i in range(k, n):
    window += a[i] - a[i - k]

答えを追跡する

スライドするたびに、それまでに見つかった最大のウィンドウの合計など、必要な値を更新します。ウィンドウの値は常にすぐ利用できます。

    best = max(best, window)

全体の計算量は線形

各要素は加算のために 1 回、削除のためにもう 1 回参照するので、全体の走査はO(n)です。大きな制約でも十分に間に合います。

インデックスに注意する

ウィンドウから出ていく要素はa[i - k]であり、a[i - 1] ではありません。このずれを正しく扱うことが、固定長ウィンドウで最もよくあるバグです。

平均も簡単に求められる

合計ではなく、ウィンドウの平均の最大値が必要ですか。その場合は、追跡しているウィンドウの合計を k で割るだけです。スライドの処理はまったく変わりません。

avg = window / k

小さな配列を処理する

配列が k より短い場合、完全なウィンドウは存在しません。最初に len(a) と k を比較して、インデックスエラーを避けるために早めに返してください。

if n < k:
    return None

固定長ウィンドウが適する場面

ウィンドウの長さが固定されている場合で、合計、個数、単純な逐次統計量のように値を効率よくまとめられるときは、このパターンを使ってください。

確認

サイズ k のウィンドウを、配列上で右に 1 ステップずつスライドさせます。

まとめ

最初のウィンドウを 1 回初期化し、その後は各ステップで加算と減算を行って O(1) でスライドさせます。固定長の全体走査は線形時間で実行できます。✅

よくある質問

「固定サイズウィンドウの合計」レッスンは無料ですか？

はい。「固定サイズウィンドウの合計」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。

「固定サイズウィンドウの合計」で何を学びますか？

長さ k のウィンドウを O(n) で移動します ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Competitive Programming Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。

「固定サイズウィンドウの合計」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCompetitive Programming Academyレッスンでコードを書いて実行できますか？

はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 固定サイズウィンドウの合計
  2. Two Pointers による可変ウィンドウ
  3. 重複のない最長部分文字列
  4. 条件を満たすウィンドウを数える
← Competitive Programming Academyに戻る