No.752 mod数列
問題
数列
が与えられる。
個のクエリに対して
を求めよ。
制約
解法
まずおなじみの累積和テクニックの考え方から
が成り立つので、任意のに対して
を求めるにはどうすればよいか?を考えることにします。
ここで程度までであれば単純に累積和でやればいいんですが、今回はですので一筋縄ではいかなさそうです。まずいきなり和を考えるのではなくて、数列がどのようになっているかを考えてみることにします。自明ではあるが重要なこととして、となっていることが分かります。よってだけで考えてみることにします。
こういうのは小さな具体例から考えてみるとよいので、としてがどのようになるかを見てみます。
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 |
0 | 0 | 0 | 0 | 4 | 0 | 3 | 0 | 6 | 4 | 2 | 0 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
すると一つ分かりやすい法則が見えます。となるにしたがっては一つずつ減っていくことが分かります。このことを式で表すととなるということが分かります。さらににも着目するとここでも規則性が見えて、が2ずつ減っていくことが見て取れます。これも式で表すととなることが分かります。
ここまで分かると一般化することが出来て、最初の自明な事実も合わせると、
任意のに対して
と表せることが分かります。ここでのときと考えることにするとつじつまが合います。
そしてこれが分かると、を固定したときの区間に含まれるに関するの総和というのは簡単に分かります。は単に区間の長さ倍すればよくの部分はおなじみのという公式を使えばよいからです。
さて、この事実が分かると何がよいのでしょうか?
任意のに対してで、この区間に対しての和はで求められます。なのでと回せばいいわけですが、までなのでこれでは計算量の削減になっていません。
しかし、までやるとしてみましょう。するとの部分に対してはこれで求められて、残りのの部分は累積和で求めてやることにすると計算量が良い感じに収まることが分かります。
後は和の上限が指定したを超えないように適宜区切ったりなんやかんやする必要がありますが、大筋のアイデアはこんな感じで計算量は今回は適当にとかにしましたが一般にはくらいにするのがいいのでに出来ます。
感想
計算量にルートが出てくる問題ってあまり無い気がして面白かったので久々に書きました。
C - Modulo Summation / ABC103
解法
まず任意のについて、であることから、の上限はであることはすぐに分かります。そして、サンプルなどを見ているとmを上手くとればをこの上限に一致させることが出来るのではないかと予想が立てられます。
実際この予想は正しくて、とすると、任意のに対してとなることが分かり、このときとなり上限に一致させることが出来ます。
感想
予想を立てるところまではすぐにいったのですが、それを証明するのに意外と時間がかかってしまいました。分かってしまえば簡単なのですが、が互いに素でないときは成り立たなかったりするのではないかと考えたり、最近知った中国剰余定理かなとか考えてしまいました。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に投げれば何とかなる
- 制約が厳しい問題がそんなに多くない(大きくてもとか)
- 分かってしまえば実装はシンプルなので定数倍もキツくない
という感じであまり障壁にならないからですね。前にも書きましたがCodeforcesは問題の傾向が割と多種多様で想定解がという問題もdiv.2-Bに出てきたりするのでpythonではまともに戦えないなと過去に思いました。(最近はめっきりこどふぉに出てないのでもしかしたら現状は変わっているかもしれないです、そうならばすみません)
pythonで競プロを始めることに対する想定される反対意見として
「pythonで競プロを始めても、そのうちpythonでは通せない問題が出てきて絶望して他の言語に乗り換えるのだからその乗換えの無駄を考えたら最初からC++とかで競プロに慣れておいたほうがいい」
というのがあって、これは一理あるかもしれません。実際私がそうで最終的にはD言語に乗換えました。こどふぉもキツいんですが、本格的にpythonでは無理だなーって思い始めたのはJOIの過去問を解いていたときですね。あれもとか普通に想定解になってたり、pythonだとメモリも食うのでそもそもMLEになっちゃって(JOIはメモリ制限もキツめです)どうしようもないなと思いました。
しかしこのデメリットは競プロをある程度やって初めて感じるデメリットです。最初から「競プロを一生の趣味にするぞ!」とか「レッドコーダーになるまでやり続けるぞ!」とか意志を固めて始める人はC++からのほうがよさそうですが、そうでないなら別にpythonでもよさそうです。どうせすぐ辞めちゃうかもしれないしね。
自分の場合は少し時間が出来てプログラミングを勉強しようかなと思って、まずpythonを覚えようと思って最初にpaizaで勉強してたんですね。paizaも一応コーディングテストみたいな、競プロっぽい問題を解けるのですがそのうち物足りなくなってyukicoderに出会いました。なんでAtCoderの前にyukicoderに出会ったのか、その経緯は覚えてませんが……ともかくその延長でpythonで競プロを始めたんですね。その後詳しく調べてみると「pythonで競プロは無理だぞ」というのが競プロ界の常識だったのですが、ひねくれているのでpythonでやっていってやるぞとか思っていました。最終的に折れちゃったんですけど。
だからといって「最初からpythonで競プロやらなければよかった……」と後悔しているかというと別にそうでもなくてですね。pythonで簡単な競プロ問題が解けるぐらいになっておくと良いこともあります。あれとかこれとか。
それでもし、あなたがpythonで競プロを始めて数か月か数年かしたぐらいに「pythonでは無理だー!」と思ったとします。そのときに乗換え先としてオススメしたいのはD言語ですね。
そもそもなんで私はD言語というマイナー言語を使っているんでしょうか。どこかで「pythonとD言語は似ているからpython競プロerの乗換先としてちょうどいい」みたいな言説を見たからだったと記憶してます。
実際似ているかと言われるとよく分かりませんが、しかし確かにD言語は使いやすいです。「pythonだったらこういうことできるのにな」と思ったことはD言語でもだいたい出来るしそれどころかあんなことやこんなことも出来る!っていうのが結構嬉しいし、使っていて楽しい言語だなと思います。それでいて実行速度も速い(10^8が余裕で通るのは本当に感動します)ので文句がありません(ホントは少しある)。デバッグもしやすいし、パソコン音痴でもインストール簡単なのでもう少し使われてもいいんじゃないかと思います。yosupoさんも使ってるし。
主題からズレたのでそろそろまとめると
ということでした。ありがとうございました。