No.752 mod数列

No.752 mod数列 - yukicoder

問題

数列
 a_i = P \% i (i = 1, 2, 3, \dots)
が与えられる。

Q個のクエリ (L_j, R_j)に対して
 \sum_{i = L_j}^{R_j} a_iを求めよ。

制約

  •  1 \leq P \leq 10^9
  •  1 \leq Q \leq 10^5
  •  1 \leq L_j \leq R_j \leq 10^9

解法

まずおなじみの累積和テクニックの考え方から

 \sum_{i = L_j}^{R_j} a_i = \sum_{i = 1}^{R_j} a_i - \sum_{i=1}^{L_j - 1} a_i

が成り立つので、任意のRに対して

 \sum_{i = 1}^{R} a_i

を求めるにはどうすればよいか?を考えることにします。

ここで R \leq 10^5程度までであれば単純に累積和でやればいいんですが、今回は R \leq 10^9ですので一筋縄ではいかなさそうです。まずいきなり和を考えるのではなくて、数列a_iがどのようになっているかを考えてみることにします。自明ではあるが重要なこととして、 i > P \Rightarrow a_i = Pとなっていることが分かります。よって i \leq Pだけで考えてみることにします。

こういうのは小さな具体例から考えてみるとよいので、 P = 24としてa_iがどのようになるかを見てみます。

i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
a_i 0 0 0 0 4 0 3 0 6 4 2 0 11 10 9 8 7 6 5 4 3 2 1 0

すると一つ分かりやすい法則が見えます。i = 13, 14, 15, \dotsとなるにしたがって a_iは一つずつ減っていくことが分かります。このことを式で表すと P > i > P / 2 \Rightarrow a_i = P - iとなるということが分かります。さらに i = 9, 10, 11にも着目するとここでも規則性が見えて、a_iが2ずつ減っていくことが見て取れます。これも式で表すと P/2 > i > P / 3 \Rightarrow a_i = P - 2iとなることが分かります。

ここまで分かると一般化することが出来て、最初の自明な事実 i > P \Rightarrow a_i = Pも合わせると、

任意の k = 0, 1, 2, \dotsに対して P / k > i > P / (k + 1) \Rightarrow a_i = P - ki

と表せることが分かります。ここでk = 0のときP / 0 = \inftyと考えることにするとつじつまが合います。

そしてこれが分かると、kを固定したときの区間 (P/(k+1), P/K)に含まれるiに関するa_iの総和というのは簡単に分かります。Pは単に区間の長さ倍すればよくkiの部分はおなじみの \sum_{i = 1}^{N} i = N(N-1)/2という公式を使えばよいからです。

さて、この事実が分かると何がよいのでしょうか?
任意の k = 0, 1, 2, \dotsに対して P / k > i > P / (k + 1) \Rightarrow a_i = P - kiで、この区間に対してa_iの和はO(1)で求められます。なので k = 0, 1, 2, \dots, Pと回せばいいわけですが、 P \leq 10^9までなのでこれでは計算量の削減になっていません。
しかし、 k = 1, 2, \dots, 9999までやるとしてみましょう。すると i > P / 10^4の部分に対してはこれで求められて、残りの i \leq P / 10^4の部分は累積和で求めてやることにすると計算量が良い感じに収まることが分かります。
後は和の上限が指定したRを超えないように適宜区切ったりなんやかんやする必要がありますが、大筋のアイデアはこんな感じで計算量は今回は適当に10^4とかにしましたが一般には\sqrt{P}くらいにするのがいいのでO(Q + \sqrt{P})に出来ます。

感想

計算量にルートが出てくる問題ってあまり無い気がして面白かったので久々に書きました。

C - Modulo Summation / ABC103

解法

まず任意のiについて、 0 \leq (m \% a_i) \leq a_i - 1であることから、f(m)の上限は \sum a_i - Nであることはすぐに分かります。そして、サンプルなどを見ているとmを上手くとればf(m)をこの上限に一致させることが出来るのではないかと予想が立てられます。

実際この予想は正しくて、 m = a_1 a_2 \dots a_N - 1とすると、任意のiに対して m \equiv -1 \equiv a_i - 1 (\mod a_i)となることが分かり、このときf(m) = \sum a_i - Nとなり上限に一致させることが出来ます。

感想

予想を立てるところまではすぐにいったのですが、それを証明するのに意外と時間がかかってしまいました。分かってしまえば簡単なのですが、a_iが互いに素でないときは成り立たなかったりするのではないかと考えたり、最近知った中国剰余定理かなとか考えてしまいました。modの世界では-1が最大になるというのは面白いですね。

実装

今回はJavaです。最近Javaの練習をしています。競プロにはやや使いづらいような印象ですが、uwiさんなどは普通に使いこなしているので凄いなと思いました。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            ans += a - 1;
        }

        System.out.println(ans);
    }
}

Pythonで競プロを始めるという選択肢

久しぶりにブログを更新します。今回は解説記事ではなく自分語り系の記事です。

twitterを見ていたら「pythonで競プロをやるってどうなの?」みたいな話が出ていたので、私も元python競プロerとして考えを述べてみたいと思います。(もともとこのブログのタイトルは「Pythonで競プロ」だった)

結論から言うと、AtCoderに限ればpythonで競プロを始めるのは普通にアリなんじゃないかなと思います。
なぜAtCoderに限定しているかというと

  • いざとなればpypyに投げれば何とかなる
  • 制約が厳しい問題がそんなに多くない(大きくても10^7とか)
  • 分かってしまえば実装はシンプルなので定数倍もキツくない

という感じであまり障壁にならないからですね。前にも書きましたがCodeforcesは問題の傾向が割と多種多様で想定解が10^8という問題もdiv.2-Bに出てきたりするのでpythonではまともに戦えないなと過去に思いました。(最近はめっきりこどふぉに出てないのでもしかしたら現状は変わっているかもしれないです、そうならばすみません)

pythonで競プロを始めることに対する想定される反対意見として

pythonで競プロを始めても、そのうちpythonでは通せない問題が出てきて絶望して他の言語に乗り換えるのだからその乗換えの無駄を考えたら最初からC++とかで競プロに慣れておいたほうがいい」

というのがあって、これは一理あるかもしれません。実際私がそうで最終的にはD言語に乗換えました。こどふぉもキツいんですが、本格的にpythonでは無理だなーって思い始めたのはJOIの過去問を解いていたときですね。あれも10^8とか普通に想定解になってたり、pythonだとメモリも食うのでそもそもMLEになっちゃって(JOIはメモリ制限もキツめです)どうしようもないなと思いました。

しかしこのデメリットは競プロをある程度やって初めて感じるデメリットです。最初から「競プロを一生の趣味にするぞ!」とか「レッドコーダーになるまでやり続けるぞ!」とか意志を固めて始める人はC++からのほうがよさそうですが、そうでないなら別にpythonでもよさそうです。どうせすぐ辞めちゃうかもしれないしね。

自分の場合は少し時間が出来てプログラミングを勉強しようかなと思って、まずpythonを覚えようと思って最初にpaizaで勉強してたんですね。paizaも一応コーディングテストみたいな、競プロっぽい問題を解けるのですがそのうち物足りなくなってyukicoderに出会いました。なんでAtCoderの前にyukicoderに出会ったのか、その経緯は覚えてませんが……ともかくその延長でpythonで競プロを始めたんですね。その後詳しく調べてみると「pythonで競プロは無理だぞ」というのが競プロ界の常識だったのですが、ひねくれているのでpythonでやっていってやるぞとか思っていました。最終的に折れちゃったんですけど。

だからといって「最初からpythonで競プロやらなければよかった……」と後悔しているかというと別にそうでもなくてですね。pythonで簡単な競プロ問題が解けるぐらいになっておくと良いこともあります。あれとかこれとか。

それでもし、あなたがpythonで競プロを始めて数か月か数年かしたぐらいに「pythonでは無理だー!」と思ったとします。そのときに乗換え先としてオススメしたいのはD言語ですね。

そもそもなんで私はD言語というマイナー言語を使っているんでしょうか。どこかで「pythonD言語は似ているからpython競プロerの乗換先としてちょうどいい」みたいな言説を見たからだったと記憶してます。

実際似ているかと言われるとよく分かりませんが、しかし確かにD言語は使いやすいです。「pythonだったらこういうことできるのにな」と思ったことはD言語でもだいたい出来るしそれどころかあんなことやこんなことも出来る!っていうのが結構嬉しいし、使っていて楽しい言語だなと思います。それでいて実行速度も速い(10^8が余裕で通るのは本当に感動します)ので文句がありません(ホントは少しある)。デバッグもしやすいし、パソコン音痴でもインストール簡単なのでもう少し使われてもいいんじゃないかと思います。yosupoさんも使ってるし。

主題からズレたのでそろそろまとめると

  • とりあえずpythonでも何でもいいから好きな言語で競プロを始めよう
  • pythonに限界を感じたらD言語に乗換えよう

ということでした。ありがとうございました。