0Pricing
Competitive Programming Academy · レッスン

Min、Max、Sum、累積合計

1 回の走査でリストを集約します

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

1回の走査で集計する

多くの問題では、配列から1つの数値だけを求めます。Pythonの組み込み関数を使えば、リストを1回走査するだけで集計を高速に行えます。

a = [4, 1, 7, 3]

合計を求める

sum(a)はすべての要素を加算し、合計を返します。C言語並みに高速なので、自分で累積ループを書くよりもこちらを優先してください。

total = sum(a)  # 15

最小値と最大値

min(a)とmax(a)は、それぞれ最小値と最大値を返します。リスト全体を1回走査するため、計算量はO(n)です。

lo, hi = min(a), max(a)

2つの数値を比較する

minとmaxには個別の引数も渡せます。max(x, y)なら、先にリストを作らずに2つの値の大きい方を選べます。

best = max(score, best)

keyで集計する

key関数を渡すと、導出した値を基準に比較できます。max(words, key=len)は辞書順で最大の単語ではなく、最も長い単語を返します。

longest = max(words, key=len)

空のリストに備える

minとmaxは空のリストでエラーになります。default=を渡すか、先に長さを確認して実行時エラーを避けてください。

hi = max(a, default=0)

累積合計の考え方

累積合計は、配列をたどりながら合計を保持します。これは累積和やさまざまなカウントテクニックの基本になります。

run = 0
for x in a:
    run += x

ここまでの最良値を追跡する

走査中にここまでの最良値を変数に保持すると、最大部分配列のような問題を1回の走査で解けます。

best = a[0]
for x in a:
    best = max(best, x)

累積和のリストを作る

すべての累積合計をリストに保存すると、累積配列を作れます。後から2つの要素を引き算することで、区間の和を求められます。

pre = [0]
for x in a:
    pre.append(pre[-1] + x)

accumulateのショートカット

itertools.accumulateを使うと累積合計を自動で生成できるため、累積配列を信頼できる1行のコードで作成できます。

from itertools import accumulate
pre = list(accumulate(a))

オーバーフローの思い込みに注意する

朗報です。Pythonの整数は上限がないため、大きな合計でもオーバーフローしません。本当のリスクは、誤った計算ではなく遅いコードです。

huge = sum(range(10**6))  # fine

クイックチェック

リスト内で最も長い単語が必要です。どの呼び出しが正しいでしょうか？

まとめ：1回の走査の力

これで、1回の走査で合計を求め、極値を見つけ、累積合計を保持できるようになりました。これらの集計によって、多くの配列問題を1つのループに置き換えられます。✨

よくある質問

「Min、Max、Sum、累積合計」レッスンは無料ですか？

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

「Min、Max、Sum、累積合計」で何を学びますか？

1 回の走査でリストを集約します ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

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

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

「Min、Max、Sum、累積合計」レッスンにはどのくらい時間がかかりますか？

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

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

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

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

  1. CP のためのリスト、インデックス、スライス
  2. 内包表記で配列を高速に作る
  3. Min、Max、Sum、累積合計
  4. 値だけでなくインデックスを見つける
← Competitive Programming Academyに戻る