Comment毎週木曜日は定例活動日です。今日はアルゴリズム入門ということで、頻出する「累積和」とその応用、「いもす法」について勉強しました。累積和とは?累積和とは、「配列のある範囲の和を高速に求めるアルゴリズム」です。以下のような大きさNの配列を考えてみましょう。和を求めたいとします。普通に考えると、for文などでA[2]からA[5]まで足し上げる以下のような実装が浮かぶと思います。何度も同じ足し算をやることになる気がするので、もう少し高速化できそうです。このような配列を考えると、任意の範囲の和を1回の計算で求めることが可能です。A[1]とすることで求められます。A[i-1]で求まります。これで求まるの?sum_A[i]という配列は、「0からiまでの要素の和」を格納しています。いうことは、この計算は「0からiまでの要素の和」から「0からj-1までの要素の和」を引いている事になり、つまりは「jからiまでの要素の和」になるのです。(sum_A[]の計算に\(O(N)\)かかります)。いもす法とは?いもす法は累積和を応用したテクニックです。いもす法は、「範囲のリストが与えられたとき、ある要素がいくつ範囲内に収まっているか」を高速に求めるアルゴリズムです。若干わかりにくいので、例を。10^7\))について、客M人がそれぞれ何時から何時までいたのかをリスト化したものがあるとしましょう。あなたの仕事は、一番客が多かった時間がいつなのかを求めることです。[N]を持っておいて、各範囲を満たす値について+1していく、というものです。sizeof(配列));は配列を特定の値(基本0か-1のみ)で初期化するものです。string.hのincludeが必要です。埋められることになってしまいます(int型は4バイト)。基本0か-1でのみ埋められると覚えておくと良いでしょう。これでは範囲が非常に大きい場合、足していく操作で非常に時間がかかってしまいます。計算量にすると、\(O(MN)\)です。累積和をどう応用する?ここで累積和の応用、「いもす法」の出番です。この問題の肝は、「入った時間と出た時間さえわかれば良い」ということです。入店した時間に+1、退店した直後の時間に-1を記録していきます。これで、累積和でやったような計算を行うと、店にいた時間が復元されます。複数重なっていても大丈夫です。することで、計算量は\(O(M+N)\)になります。コードに起こしてみましょう。...}演習さて、累積和といもす法を使う問題をいくつか紹介しておきます。Coffee」いずれも累積和といもす法で解けます。「オセロ」の問題と、解法も紹介しておきます。N個の黒を向いたオセロコマが並んでおり、l個目からr個目までのコマを裏返す操作をQ回行います。このとき、コマの並びを出力する、というものです。裏返した回数をimos[]に記録し、その偶奇で0と1を表示させればOKです。0;}そろそろ文化祭でみんなも忙しそう。私も他のサークルのコーディングで死にそうです。コメントをキャンセルメールアドレスが公開されることはありません。