10^8 の経験則
演算回数を制限時間に当てはめます
「10^8 の経験則」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。
魔法の予算
一般的なオンラインジャッジは、1秒あたり約10^8回の単純な操作を実行できます。この数値が、プログラム全体で使える処理量の目安です。💡
ステップ数を秒数に換算する
操作回数に1ステップあたりの処理量を掛け、その結果を制限時間と比較します。ステップ数が予算内に収まれば、通過できる可能性が高いでしょう。
線形時間は余裕がある
n = 10^6 に対する O(n) の走査は、わずか100万ステップで、予算を大きく下回ります。線形解法なら、ほとんどの場合、十分な余裕を持って通過できます。
n log n なら安全
n = 10^6 の場合、O(n log n) のソートは約 2 × 10^7 ステップです。1秒の予算内に十分収まるため、ソートがボトルネックになることはほとんどありません。
二次時間には上限がある
O(n^2) の方法は、10^8ステップになる n = 10^4 付近で予算に達します。それを超えると、二次時間の処理は時間切れになり始めます。
三次時間は小さい n でのみ使える
O(n^3) の解法で処理できるのは、n が約500までです。500を3乗するとおよそ10^8ステップとなり、予算の限界に達します。
指数時間は小さい n に限る
O(2^n) はステップごとに2倍になるため、n が20〜25程度の小さい場合にしか使えません。それを超えると、操作回数は10^8をはるかに超えて急増します。
Python には処理の負担がある
Python は1ステップあたりの処理が遅いため、タイトなループでは予算を10^7程度と考えてください。制約がぎりぎりに見える場合は、余裕を持って判断しましょう。
隠れた定数倍に注意する
10^8という目安は単純なステップを数えたものです。文字列の構築など、ループ内で重い処理を行うと定数倍が増え、実際に使える予算は小さくなります。
制限時間を確認する
制限時間は1秒または2秒であることが多いです。2秒の制限時間なら、予算はおおよそ2倍になり、少し余裕が増えます。
入力する前に見積もる
まず n を計算量の式に代入し、10^8と比較してください。この簡単な妥当性チェックを行えば、最初から通らない解法を実装せずに済みます。
確認問題
10^8のルールを実際に使ってみましょう。
復習
操作回数を時間に換算できるようになりました。目安は1秒あたり約10^8回です。線形時間と n log n は安全で、二次時間は n = 10^4 付近が上限です。コーディング前に確認しましょう。✅
よくある質問
「10^8 の経験則」レッスンは無料ですか？
はい。「10^8 の経験則」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。
「10^8 の経験則」で何を学びますか？
演算回数を制限時間に当てはめます ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Competitive Programming Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「10^8 の経験則」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCompetitive Programming Academyレッスンでコードを書いて実行できますか？
はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。