区間を伸ばし、条件を直す
スライディングウィンドウは、連続した区間の状態を保ちながら左右の境界を動かす方法です。ここでは二つの問題を扱います。一つ目は、非負の整数列から和が目標以上になる最短の区間を探す問題です。二つ目は、文字列から異なる文字の種類数がk以下となる最長の区間を探す問題です。どちらも区間を一から数え直す代わりに、右へ入る要素と左から出る要素で状態を更新します。
ただし、二つの問題で縮める条件と答えを更新する時点は同じではありません。最短の和では、条件を満たす間に長さを記録して左を進めます。種類数の最長区間では、条件を破る間に左を進め、直した後の長さを記録します。「窓を使う」という名前だけでこの順序を決めず、どの区間を有効とみなすかから導きます。
非負の和で最短区間を追う
配列2、1、3、2、目標5を考えます。右を進めると和は2、3、6となり、最初に長さ3の区間が条件を満たします。左の2を外すと和は4になり、それ以上縮められません。次の2を加えると和6、区間は1、3、2です。長さ3を記録し、左の1を外すと和5で長さ2も候補です。さらに3を外すと和2になり終了します。最短は3、2の二要素です。
非負という前提により、右へ要素を加えると和は減らず、左を外すと増えません。ある左端を捨てた後で、その左端を戻さないと見つからない短い解が生じないことを、この単調性から説明します。ゼロは許しますが、targetは正に限定します。ゼロの要素が続いても左を進める回数は有限です。空区間を答えに含める別の仕様とは区別してください。
| 追加後の右位置 | 縮小の途中 | 記録する長さ |
|---|---|---|
| 2:値3を追加 | [2,1,3]の和6→[1,3]の和4 | 3 |
| 3:値2を追加 | [1,3,2]の和6→[3,2]の和5→[2]の和2 | 3、次に2 |
種類数には頻度表が必要になる
文字列abac、上限k=2なら、a、ab、abaまでは有効です。cを加えたabacは三種類なので左を縮めます。最初のaを外してもbacにはaが残り、三種類のままです。次にbを外してacになった時点で二種類へ戻ります。最長はabaの長さ3です。単なる文字の集合からaを消してしまうと、区間内にもう一つaがあることを失うため、出現回数を保存します。
左から出した文字の回数を一つ減らし、ゼロになったときだけ辞書のキーを消します。辞書の要素数が現在の種類数です。k=0では全ての非空区間が条件を破るので、修復後の長さは0になります。ここでいう文字はPythonの文字列の要素で、見た目の一文字を表す書記素クラスタとは限りません。絵文字や結合文字を数える製品要件へ移す場合は、分割単位を先に決めます。
二つの実装を参照解と比べる
付属コードは和の入力に負数があればValueErrorで拒否します。これは扱える入力の契約を明示するためで、負数をゼロへ置き換える補正ではありません。短い非負配列の全区間を調べ、条件を満たす長さの最小値と一致することを検査します。文字列の方も全ての部分文字列を調べる参照解と比較します。空配列、答えの不在、ゼロの値、k=0を含めてください。
最短区間が存在しない場合の返り値は0とします。区間そのものや添字を返す設計なら、最短値を更新した時点の左右も記録する必要があります。同じ長さの候補が複数あるときは、最初のものを返すか全て返すかを決めます。今回のコードは長さだけを返すため、その選択は出力へ現れません。返り値の意味とテストの期待値を対応させることが大切です。
from itertools import product
def minimum_length(a,target):
if target<=0 or any(x<0 for x in a):raise ValueError('nonnegative values, positive target required')
left=0;total=0;best=len(a)+1
for right,x in enumerate(a):
total+=x
while total>=target:
best=min(best,right-left+1);total-=a[left];left+=1
return 0 if best>len(a) else best
def distinct_window(text,k):
if k<0:raise ValueError('negative limit')
counts={};left=0;best=0
for right,c in enumerate(text):
counts[c]=counts.get(c,0)+1
while len(counts)>k:
old=text[left];counts[old]-=1;left+=1
if counts[old]==0:del counts[old]
best=max(best,right-left+1)
return best
for n in range(6):
for a in product(range(3),repeat=n):
for target in range(1,5):
sizes=[j-i for i in range(n) for j in range(i+1,n+1) if sum(a[i:j])>=target]
assert minimum_length(a,target)==min(sizes,default=0)
for text in ['','abac','aaaa','abcabc']:
for k in range(4):assert distinct_window(text,k)==max((j-i for i in range(len(text)+1) for j in range(i,len(text)+1) if len(set(text[i:j]))<=k),default=0)
try:minimum_length([2,-1],2)
except ValueError:pass
else:raise AssertionError('negative input accepted')
print('sum and distinct-count windows matched exhaustive references')
負数を加えると、和の判断が崩れる
配列1、−1、5、目標5を考えます。全体の和5に達したとき、先頭の1を外すと和4になります。非負用の実装はそこで縮小を止め、長さ3を候補とします。しかし次の−1も外せば和は5へ増え、最後の5だけで長さ1の解があります。左を外すと和が増える場合があるので、「小さくなったから縮小を終える」という判断が成立しません。
この反例は、どんな窓でも負数を扱えないという意味ではありません。異なる文字数を追う窓は、そもそも数値の和へ依存しません。負数を含む最短区間和なら、累積和や別の候補管理を検討します。技法の名称で可否をまとめず、右を足したとき、左を外したとき、維持する尺度がどちらへ動くかを確認します。条件が変わったら、不変条件から設計をやり直してください。
入れ子のwhileでも線形になる理由
右端は各要素を一度ずつ追加します。左端も戻らず、各要素を高々一度だけ取り除きます。内側のwhileを各右端でn回と掛け合わせるのではなく、処理全体で取り除かれた要素の総数を数えると、和の実装はO(n)です。辞書の操作を平均O(1)とみなす文字列版も同じ数え方ができます。頻度表の領域は区間内の異なる文字に比例し、使用する文字集合の大きさにも制約されます。
ただし、毎回部分配列をコピーしたり、区間の和をsumで計算し直したりすれば、この費用の説明は変わります。コードのtotalへ加減算している箇所と、辞書の一要素だけを更新する箇所を確認してください。理論の状態更新と実装の操作が対応して初めて、端が一方向という性質を実行費用へ結び付けられます。大きな整数や高価なキー比較の費用は、選んだ計算モデルの外へ隠さず補足します。
状態の更新を一つずつ照合する
窓の誤りを調べるときは、leftとrightだけでなく、現在のsumや頻度表も各段階で紙の区間へ照合します。たとえばabacで最初のaを外した後、辞書のaが1残ることを確かめます。境界は合っていても、削除時のカウントを間違えれば、次の縮小の判断が変わります。短い入力へ全区間の参照解を用意する理由は、この内部状態の誤りが最終の長さへ現れる例を広く探せるためです。
複数の制約を同時に課す場合も、どの状態を持ち、どちらの方向へ修復できるかを再確認します。最長の区間でも、有効になった瞬間に必ず左を一つ進めるわけではありません。長く保つべき局面と縮めるべき局面を目的から導きます。名前の似た窓のコードを移植する前に、各変数の意味と答えを更新する時点を短い表へ書くと、条件の取り違えを見つけやすくなります。
演習:条件と答えを更新する位置を確かめる
課題は文字列aabcc、k=2について、各右端で修復後に残る区間と最長値を書くことです。解答の区間はa、aa、aab、bc、bccで、最長値は1、2、3、3、3です。最初のcを加えたaabcからaを一つ外しても、まだa、b、cの三種類です。二つ目のaを外して初めてbcへ直ります。通知回数のような外部の履歴ではなく、現在の頻度表で条件を判定してください。
追加課題は、非負の配列0、0、5と目標5です。和が5へ達した後にゼロを二つ外しても条件が保たれ、最短は最後の一要素です。whileをifへ変えると、一回しか縮めないためこの答えを逃し得ます。解答では「whileが必要」と暗記せず、一つの右端に対して有効な左端が複数あり、さらに短い候補を調べる必要があると説明します。