【C#】累積和を実装してみた AtCoder Beginner Contest 084 D問題

AtCoderやっていると、累積和もよく出てくるため実装してみました。400点のD問題を答えを見ずに解けたのはすごく良かった。(累積和を使うというのは知っていたので微妙なところですが)

atcoder.jp

結果

コード

github.com

累積和とは

下記の記事が非常に分かりやすいと思います。 qiita.com

"累積とはなにか"というポイントと"累積和はどういったときに使用するのか"というポイントをここで抑えておいて、あとは問題に出会ったときにちゃんと累積和を使用することに気がつけるかどうかです。

といっても、まだ学んだばかりで知識はまだ浅いのですが、現状において考えていることを書こうと思います。

どんなタイミングで使用するのか

適切な前処理をしておくことで、配列上の区間の総和を求めるクエリを爆速で処理できるようになる手法

とあります。前処理をしておけば、O(1)でクエリを処理することができます。なので、累積和を使用する条件として、下記をあげようと思います。

1. 配列上の区間に紐づく何かしらの値を求める問題
2. 多くのクエリが実行される可能性がある問題

1つ目ですが、参考サイトには総和を求めると記述がありますが、総和とか考えず、一旦配列のとある区間の何かしらの値を求めると考えてみるといいかなと思います。

2つ目ですが、これはクエリを爆速処理するために前処理をするのでクエリが多い方が効果は非常に大きいです。

正直、2つ目は必ずしも判明している部分ではないと思うので、個人的には配列区間の値を求めることがあったらまず累積和を疑うでいいんじゃないかなと。逆に、問題を配列区間の問題に落とし込めるなら累積和という考え方もありかなと。

ABC084 D問題の実装

考え方 & 解法

この問題は、ポイントが2つあります。まず1つ目。これは、累積和を使うということ。上記の条件に当てはめてみると今回の問題は累積和を使用することがわかると思います。

• クエリQが 1≦Q≦10⁵ である
• l_i ≦ x ≦ r_i かつ 2017に似た数 となる奇数 x の個数

このように、与えられた l から r の区間である条件に合致する奇数xの個数を求めるという条件が見事に最初に記載した累積和を使用する条件に合致します。

2つ目ですが、これは素数がどうか判定する方法です。

• Nも(N+1)÷2も素数

という条件が与えられているため、素数かどうかを判定する方法が必要です。

今回は、フェルマーの小定理を使おうかと考えたのですが、最悪で2016²⁰¹⁷の計算をする羽目になりそうだったので別の方法で実装しました。

素数には、"素数かどうか判定するためには、その素数の平方根以下の素数で割り切れるかどうかを調べれば判定できる"という性質があるのでこれを利用しました。

static bool IsPrimeNumber(int number)
{
    double i = number;
    // 平方根を求める
    double x = Math.Sqrt(i);
    // 平方根以下の値で割り切れるのか確認する
    // 最小値は2
    for (double j = 2; j <= x; j++)
    {
        if ((number % j) == 0) { return false; }
    }
    if (number == 1) { return false; }
    return true;
}

まとめ

実装していると、添字の扱いにやや困ったのでちゃんとロジックを立てて実装して、それから検証して～というのを繰り返して行きたい。今回も最初WAを出したけど、AtCoderの問題で表示されている例だけじゃなくて自分でテストケース作っておけば事前に気がつけたはず。