ひとりで勝手にはじめた蟻本読書会 二分探索法 平均の最大値を求める 蟻本読書会 の続きです。
しゃくとり法は区間の左端と右端を尺取り虫のように動かすことで、条件を満たす区間を高速に見つけるアルゴリズムです。条件を満たす連続する部分列のうち、最大・最小の長さを求めよ、条件を満たす連続する部分列を数え上げよという問題に対して有効です。
しゃくとり法は原理的には難しくないのですが、実際に実装しようとすると頭がこんがらがってしまいます。落ち着いて実装しましょう。
Contents
区間長の最大値・最小値
長さ N の非負整数列 S = s_1, s_2, …, s_N と整数 K があります。 あなたの仕事は「その部分列に含まれる全ての要素の値の積は、K 以下である」という条件を満たす S の 連続する部分列のうち、最も長いものの長さを求めることです。部分列の長さは 1 以上の列でないといけません。もし条件を満たす部分列が一つも存在しないときは、0 を出力してください。
入力されるデータ
N K
s_1
s_2
:
s_N（ただし、1 ≦ N ≦ 10^5
0 ≦ K ≦ 10^9, 0 ≦ s_i ≦ 10^9 ）
s_1, s_2, …, s_N が何であってもそのなかに 0 が存在するならその積は 0 です。K ≧ 0 なのでこの場合は N が解となります。
それ以外の場合は変数 left と right を 0 で初期化して、半開区間 [a, b) （a 以上 b 未満）を以下のような方法で動かします。
temp に A[right] を掛けたときに K を超えないなら実際にtemp に A[right] を掛けて right をインクリメントする処理を繰り返します。この繰り返し処理ができなくなったときが left に対する right の最大値であり、right – left が解の候補となります。
right が動かせなくなったら left を 動かします。temp は s[left] * s[left + 1] * … * s[right] なので left をインクリメントする前に temp /= A[left] を実行します。ただし、left が right に追いついてしまった場合はなにもしないで right をインクリメントします。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N, K; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; K = vs[1]; } int[] A = new int[N]; for (int i = 0; i < N; i++) A[i] = int.Parse(Console.ReadLine()); long temp = 1; int right = 0; int max = 0; for (int left = 0; left < N; left++) { // right を 1 個進めたときに条件を満たすか確認したあと 実際に right を 1 進める while (right < N && temp * A[right] <= K) { temp *= A[right]; right++; } // while 文から抜けた段階で right は条件を満たす最大値なので、これを保存する max = Math.Max(max, right - left); if (temp == 0) { max = N; break; } // left をインクリメントする準備 if (right == left) right++; else temp /= A[left]; } Console.WriteLine(max); } } |
区間の数え上げ
N 個の数からなる数列が与えられます。i番目の数を a[i] と呼びましょう。
a[l], a[l+1], …, a[r] が単調増加となる (l, r) の数を求めてください。入力されるデータ
N
a[1] a[2] … a[N]
（ただし、1 ≦ N ≦ 10^5, 1 ≦ a[i] ≦ 10^5 ）
半開区間 [a, b) を尺取虫のように動かすのは前問と同じですが、動かし方が少し異なります。最初の項を a[left] として right を単調増加でありつづける限り増やしていくのですが、単調増加でなくなったとき次のループ処理の left の値は単調増加でなくなったときの right の値に一気に増やすことができます。
left と right が動かなくなって無限ループになったり、left の値が right を追い越してしまわないように注意します（ループの最後に left = Math.Max(right, left + 1); right = Math.Max(right, left + 1);でよいかと・・・）。
単調増加である left と right の値が定まったらそのあいだの区間の種類は 1 から (right – left) までの総和だけ存在します。なので以下のようなコードになります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); long ans = 0; long left = 0; long right = 1; while (left < N) { int temp = A[left]; while (right < N && temp < A[right]) { temp = A[right]; right++; } ans += (right - left + 1) * (right - left) / 2; left = Math.Max(right, left + 1); right = Math.Max(right, left + 1); } Console.WriteLine(ans); } } |
長さ N の整数列 A があります。次の条件を満たす整数 left, r ( 1 ≦ left ≦ right ≦ N ) の組の個数を求めてください。
A[left] xor A[left+1] xor … xor A[right] = A[left] + A[left+1] + … + A[right]
入力されるデータ
N
A_1 A_2… A_N
（ただし、1 ≦ N ≦ 2 × 10^5, 0 ≦ A[i] ≦ 2^20 ）
xor が難しそうですが、演算子 ^ を使えば簡単に求めることができます。あとはしゃくとり法でやればOK。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int xor = 0; int sum = 0; int right = 0; long ans = 0; for (int left = 0; left < N; left++) { while (right < N && (xor ^ A[right]) == sum + A[right]) { xor ^= A[right]; sum += A[right]; right++; } ans += right - left; if (right == left) right++; else { xor ^= A[left]; sum -= A[left]; } } Console.WriteLine(ans); } } |
