制約を読み、計算量を選ぶ

すべての問題には、n や値の制限が示されています。こうした制約から、出題者が想定している計算量を読み取れます。🔍

何かを設計する前に、制約における最大のnを確認してください。n の大きさによって、二次時間、線形時間、対数時間のどれが必要かが決まります。

n が20以下なら、指数時間の全探索でも処理できます。制約が小さい場合は、恐れずにすべての組み合わせを試してみましょう。

n が数百に達する場合でも、O(n^3) の解法なら通過できます。三重ループや、要素のペアに対する基本的な DP も使える範囲です。

n = 5000 前後なら、O(n^2) を目標にしてください。配列に対する二重ループは約 2.5 × 10^7 ステップとなり、まだ予算内に収まります。

n が 10^5 や 10^6 に達する場合は、O(n log n) または O(n) が必要です。ソート、累積和、尺取り法が定番の道具になります。

n が10億なら、n 回のループは通用しません。数学的な方法や答えに対する二分探索を使い、O(log n) または O(1) にする必要があります。

値に関する制約も重要です。大きな数は、他の言語ではオーバーフローに注意する必要があることを示し、剰余算を使うヒントになる場合もあります。

複数テストケースの問題では、各 n ではなくn の合計に上限が設定されることがよくあります。ループを安全にどこまで大きくできるかが変わるため、注意して読んでください。

n から目標とする計算量を決め、その計算量を実現できるアルゴリズムを選びます。n に設計を導いてもらう方が、推測して後から書き直すよりも効率的です。

この表を頭に入れておきましょう。制約と計算量の対応表があれば、コンテスト中に制約をざっと見るだけで、すぐに方針を立てられます。

n から適切な計算量を判断してみましょう。

制約を目標として読めるようになりました。小さい n なら全探索、10^5 なら n log n、10^9 なら log または数学的な方法が必要です。n に方針を選ばせましょう。🗺️