Holograph1c Attract0r

日々の数学やプログラミングに関係する話。

競プロで悩んだ計算量の話

競プロの精進をしていて、個人的に悩んだことがあったので書いておきます。
誰かの助けになれば、と思います。

※各問題の解法ネタバレ有り

ABC097 C - K-th Substring

問題概要:
文字列 s が与えられる。s の部分文字列のうち、辞書順で K 番目に小さいものを出力せよ。
|s| \leq 5000

N = |s| とします
基本方針としては、制約が小さいのでC++ならsetにでも突っ込んで順番に取り出せばよいです。setはデフォルトでソートされた状態で保持してくれますからね。

というわけで一番最初に提出したコードがこちら。

Submission #11947075 - AtCoder Beginner Contest 097

うん、ループは O(N ^ 2) だしsetへのinsertは対数オーダーだから通るはず……って言ってると、なぜかTLEに。さて、なぜでしょうか。

強い人に質問してみると、これ実は O(N ^ 3 \log N) になってるらしいとのこと。

どこで O(N) が発生しているかというと、文字列の比較でした。
文字列の比較なんてどこでした?という感じなのですが、よく考えてみるとsetへinsertするときに毎回発生しています。ソートされた状態で要素を保持するためには比較をしなければなりませんからね……。これが盲点でした。
ソートをする際、比較そのものの回数は O(\log N) なわけですが、その比較1回あたりに O(N) かかっていたわけです。(正確には比較する文字列の長さのmin?)

そんなわけで、もうちょい計算量を削らなければなりませんが、この問題の場合には K の制約が小さいおかげで、長さ6以上の部分文字列はsetへinsertしないことによりTLEを回避できました。

ACコード(1行追加しただけ):
Submission #11947828 - AtCoder Beginner Contest 097

ABC162 E - Sum of gcd of Tuples (Hard)

問題概要:
1 以上 K 以下の整数からなる長さ N の数列の全てについてgcdを求め、その和を計算せよ。
2 \leq N \leq 10 ^ 5, 1 \leq K \leq 10 ^ 5

基本方針は公式解説の通りで、1 \leq X \leq K に対して最大公約数が X となるような数列の数を求めてその和を求めます。

こちらが書いたコード。
Submission #11975132 - AtCoder Beginner Contest 162

注目してほしいのは、もちろんループの部分。

for (int x = k; x > 0; x--) {
    lint t = k / x;
    t = modpow(t, n);
    lint x2 = x + x;
    while (x2 <= k) {
        t -= c[x2];
        x2 += x;
    }
    t = ((t % MOD) + MOD) % MOD;
    c[x] = t;
    res += t * x;
    res %= MOD;
}

内側のwhileで、倍数の分の数を引いています。
ここで気になるのが、このwhileループ、計算量はどうなるの?ということです。 ACを出したときはよく分かっていないまま通ってしまったのですが、別にTLEとなってもおかしくなかったと思います。
ここで今一度、ループの実行回数を考えてみます。

whileループの回数は、コード中の変数 x の値に依存しています。具体的には、x の倍数の個数の分だけ、ループが実行されるはずです。

ということは、x = k のときは \frac{k}{k} 回、x = k-1 のときは \frac{k}{k-1} 回、…という風になるので(本当は小数点以下切り捨てですがあえてこう書きます)、全体でのループの回数は以下の和になるはずです。

\frac{k}{k} + \frac{k}{k-1} + \frac{k}{k-2} + \cdots + \frac{k}{2} + \frac{k}{1}

もうこう書いてしまったら分かりやすいのですが、これを k でくくります。
そうすると、こうです。

k \cdot \left( \frac{1}{k} + \frac{1}{k-1} + \frac{1}{k-2} + \cdots + \frac{1}{2} + \frac{1}{1} \right)

右の分数の和は第 K 調和数 H_K なので、これは \log K に近似することが出来て、最終的な計算量は O(K \log K) ということになります。

コンテスト中にここまで思考を詰めれる人、すごいな……。