連続する区間の和

与えられたint型の配列において、長さが 1 以上で総和が与えられた値以下であるものを考えます。そのような区間がいくつあるか、区間の長さで最大のものを求めるにはどうすればいいでしょうか?

(例)int[] a = {4, 5, 6, 8, 2, 6, 7, 4, 2, 15,} 区間の和が15以下のものを対象にするのであれば、

a[0] + a[1] = 9 とか a[1] + a[2] = 11 とか a[0] + a[1] + a[2] = 15 などが対象となります。配列のなかで連続しているもののみが対象です。a[0] + a[1] + a[4] = 11 のように連続していないのであれば和が15以下でも対象とはしません。

最初に left と right を 0 にしておいて a[left + 0] + a[left + 1] + (中略) + a[right] が15以下であるかぎりrightを大きくしていきます。和が15を超えたらleftをひとつ増やして rightはleftの位置に戻します。こうしてleftとrightがしゃくとり虫のように両者の距離を広げたり縮めたりしながら右のほうへ移動していきます。配列上の同じような場所の和を何度も計算するので累積和と組み合わせて使うと処理時間を短縮できるかもしれません。

配列から累積和が格納された配列を求める処理を示します。

累積和から arr[min] から arr[max]までの和を求める処理を示します。

あとはこれらのメソッドを用いてしゃくとり法で区間の和を計算します。

結果は区間の和が15以下の区間は16個、最大長は3、区間の和が15より大きい区間の最短長は2であることがわかりました。

(参考)しゃくとり法の練習問題

単純増加の数え上げ

配列内において、連続する部分列のうち広義単調増加となっている区間を数え上げます。広義単調増加とは、a_i ≦ a_(i + 1) (l ≦ i < r) あるか、要素が1つの部分列のことを指します。たとえば int[] a = { 6, 5, 1, 3, 2, 1, 2, 3,} であれば a[5] ~ a[7] だけでなく a[5] ~ a[6]、a[6] ~ a[7]のようなものもカウントします。それから要素が1つの場合も広義単調増加なので a[0] だけ、a[1] だけであっても対象となります。 Showメソッドは、第一引数で渡された配列のなかの、第二引数と第三引数で囲まれた部分の要素をカンマ区切りで表示するためのものです。

arr[max - 1] と arr[max] を比較すればよいのですが、要素数が1のときは無条件で広義単調増加とみなすので、その場合(min == maxのとき)は別に処理が必要です。それ以外の時は arr[max - 1] ≧ arr[max] であれば広義単純増加なので max をインクリメントし、そうでない場合は min をインクリメントして max に min を代入します。max が最後まで来たら、この場合もmin をインクリメントして max に min を代入します。これで調査対象をすべて調査できます。

(参考)しゃくとり法の練習問題

同じものが存在しない区間の長さの最大値

問題:さまざまな色の服が一列に並べられて売られています。色は整数で表わされています。ある区間の服をまとめ買いしたいと考えているのですが、同じ色の服は買いたくありません。同じ色が 2 箇所以上存在しない区間のうち、最大の長さを求めよ、という問題が出てきたらどうすれえばいいでしょうか?

min と max をしゃくとり虫のように動かして配列の最後まで調べるのですが、区間内に同じ色の服があるかどうやって調べればよいのでしょうか? 鳩でもわかるC#管理人は辞書の性質を利用しました。

すでに辞書内にあるキーと同じキーでAddメソッドを呼び出すと例外が発生します。もし例外が発生したら重複があるとみなし、辞書内のデータはすべて削除、min をインクリメントします。例外が発生しない場合は区間内に同じ色の服はないので max をインクリメントするとともに 辞書内の要素数が maxLength を超えていたら更新します。max が配列の最後にきた場合も区間内に同じ色があったときと同じ処理をおこないます。

(参考)しゃくとり法の練習問題