hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

TopCoder SRM 723 Div2 Hard: SimpleMazeEasy

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

 N \times N の部屋が十字型に並んでいる。 (詳細は原文をご覧ください)

すべての部屋と部屋の間の最短距離の総和を求めよ。

解説

ちゃんとした解説は kmjp さんのブログ にあります。

変数が  1 つしかないので、愚直解で最初の方を求めて OEIS したい気分になります。

というわけで愚直解を書くと、  16, 600, 4680, 19904, 61000, 152136 \dots になることが分かるため、それを投げます。

しかしこの数列は OEIS にはありません (悲しいね)

ところでこの場合の数はどんなオーダーで増えていくでしょうか?

まず、点は  O(N^{2}) 個あります。その点とペアになりうる点もまた  O(N^{2}) 個あります。そして、ペアとの距離は  O(N) です。ということで、 O(N^{5}) 程度の多項式になりそうである予想が (プロは) 思いつきます (自分は思い付きませんでした)

この過程と先ほどの愚直解から、  f(x) = c_{5} x^{5} + c_{4} x^{4} + c_{3} x^{3} + c_{2} x^{2} + c_{1} x + c_{0} を †ニュートン補間† や †ラグランジュ補間† などで気合で求めると  O(1) で解くことができます。

ソースコード

long long mod_pow(long long N, long long K) {
    long long t = N % MOD, ret = 1;
    while(K) {
        if(K & 1) (ret *= t) %= MOD;
        (t *= t) %= MOD;
        K >>= 1;
    }
    return ret;
}

class SimpleMazeEasy {
    public:
    int findSum(long long n) {
        long long vl = (333333332LL * mod_pow(n, 3)) % MOD;
        long long vr = (666666691LL * mod_pow(n, 5)) % MOD;
        return (int)((vl + vr) % MOD);
    }
};

OEIS パンチできなかったら多項式を推定する方法もあるという知見は得られましたね・・・