制約から計算量を見積もる

正しくても時間内に終わらなければ TLE です。秒数の断言ではなく、入力が増えたときの処理回数を比べます。

言語：Python / 計算量：O(N²) と O(N log N) を比較

前提：関数で手順を切り出す

考え方

1. 1回の走査は O(N)。
2. 二重ループは各 N 回なら O(N²)。
3. N=200000 の二重ループは約400億回。まずアルゴリズムを変えます。

具体例

N=1000 なら N²=100万。N=100000 なら100億。同じコードでも入力規模で現実性が変わります。

実装

n = 100
count = 0
for i in range(n):
    for j in range(n):
        count += 1
print(count)

注意する条件

「Pythonは1秒で必ず何回」は成り立ちません。処理内容・処理系・メモリ・制限時間を確認します。

確認問題

N=100 の二重ループ N×N は何回？

実装課題

N (1 ≤ N ≤ 10^9) を読み、1 から N の総和をループなしで求めてください。

入力:
5
出力:
15

n = int(input())
print(n * (n + 1) // 2)

実戦につなげる補講

一度に全て読まなくて大丈夫です。今日は1節と1問から。

1. 最初に数えるのは、コードの行数ではない

Nはデータの個数、Qは質問の回数、Vは値の最大など、制約欄に登場する量を区別します。N=20万でも、値が10億なら値の大きさ分の配列は別の問題です。

制約を見たら「最大の入力で、この行は何回動く？」と声に出してみます。forが1個か2個かではなく、その中でsum・検索・コピーを何回するかまで数えます。

2. 足し算と掛け算を使い分ける

N回の処理を終えてからM回の処理をするならN+M。N個それぞれに対してM個すべてを調べるならN×Mです。N=M=200000なら後者は400億回。小さな入力で動いても、最大入力では別物になります。

i<jの全組合せはN(N−1)/2回です。半分にはなりますがO(N²)のまま。候補を半分にする工夫と、増え方そのものを変える工夫を区別します。

3. O記法は「増え方」の要約

O(N)はNを2倍にしたとき処理の主要部分もおよそ2倍、O(N²)ならおよそ4倍になる増え方です。O(N log N)のlogは何回半分にできるかの目安。log₂200000は約18です。

O記法では定数倍や小さな項を省きますが、実行時間では消えません。Pythonのループ、組み込み関数、大きな整数の計算では1回の重さが違います。「1秒で必ず何回」は暗記しません。

4. 制約は解法を断定する表ではない

Nが20なら2^Nは約100万、Nが40なら約1兆です。Nが200000ならN²をまず疑い、O(N)やO(N log N)にできないか考えます。これは候補を絞る目安で、時間内の保証ではありません。

複数テストケースがあるなら、それぞれの処理回数を合計します。NとQが両方大きい場合は、NだけでなくN×Qも必ず見ます。

5. 速くする前に、繰り返しの正体を言う

「毎回、同じ区間の合計を足し直している」なら集計の再利用。「同じ値があるか列を端から探している」なら集合。「すべての相手と比較している」なら順序付けや境界探索。「同じ状態の続きを何度も解いている」ならDPが候補です。

今は名前を覚えなくても構いません。どの情報を保存すれば、次に同じ仕事をしなくて済むかを考えます。各技法の講義を学んだあと、この節に戻ってください。

6. 1行に隠れたループを見つける

sum(a[l:r])は定数時間ではありません。スライスで区間をコピーし、sumで要素を走査します。これをQ回行えば最悪O(NQ)。x in aもaがリストなら最悪O(N)、setなら通常は平均O(1)ですが構築に平均O(N)かかります。

ループ中のsorted(a)、list.count、pop(0)、長いリストのコピーを探します。見た目を短くするだけでは計算量は減りません。

7. メモリも制約の一部

N=200000の要素を1列持つのと、N×Nの表を持つのは違います。後者は400億マスです。Pythonの整数やリストは値以外の管理領域も使うため、「マス数×8バイト」だけで見積もらないようにします。

時間を減らすために全ての質問の答えを保存すると、メモリが先に足りなくなることがあります。必要な情報だけを保持する設計にします。

8. コンテストで使う5行メモ

①最大のN・Q。②まず正しい愚直解。③最大処理回数。④繰り返している無駄。⑤改善後の時間・メモリ。この5行を書いてから本実装へ進みます。

小さな入力では愚直解を正解確認用に残します。速い解と100個ほどの小さいランダム入力で比べ、最後に最大付近の入力で実測します。実測だけで正しさや最悪計算量を証明したことにはなりません。

段階式の追加演習

1. 回数を手で数える

N=5で、iを0〜4、jをi+1〜4として全組合せを調べる。内側の処理は何回？ N=200000なら？

2. 短いコードの落とし穴

長さNのリストに対し、Q回sum(a[l:r])する。前処理なしの最悪計算量は？

3. 二重ループでも線形？

r=0をループの外で初期化し、各lについてwhileでrを増やす。ただしrは戻らずN以下。while本体の総回数は？

4. 制約が変わったら方針も変える

長さNの列の区間和をQ回答える。N=100,Q=1とN=200000,Q=200000で、方針を説明して。

公式過去問への橋渡し

ABC212 C / 公式解説

2つの列から選ぶ全組合せは最大400億組。ソート後に比較対象を減らす判断を練習する。

ABC248 D / 公式解説

値ごとの出現位置を保存し、区間の境界を二分探索する。前処理と質問処理を分けて数える。

見本を閉じて確認

• N・Q・値の上限を区別できる
• スライス・sum・inの内部処理も数えられる
• 愚直解の無駄を言葉にできる
• 高速化後の計算量を実装から説明できる

読了の記録・下書き・メモへ