尺取り法

code: TwoPointers.js

/* 尺取り法 */

class TwoPointers {

init(func) {

if (this._init==null) return this._init;

this._init = func;

return this;

}

add(func) {

if (this._add==null) return this._add;

this._add = func;

return this;

}

remove(func) {

if (this._remove == null) return this._remove;

this._remove = func;

return this;

}

cond(func) {

if (this._cond == null) return this._cond;

this._cond = func;

return this;

}

value(func) {

if (this._value== null) return this._value;

this._value= func;

return this;

}

search(arr) {

const ret = [];

for (let l = 0, r = 0;; ++l) {

for (;r < n && !(this.cond()); ++r, this.add(r));

if(!func.cond) break;

ret.push({ l:l,r:r, v: this.value() });

this.remove(l)

}

return ret;

}

}

サンプル

AtCoder ABC032 C - 列

code: abc032_c.js

class Main {

solve() {

const nk = input.nextIntArr();

const tp = new TwoPointers();

const res = tp

.init(() =>{tp.v = 1;})

.value(() => tp.v)

.searchMax(seq);

if (res.length == 0) { return 0; }

return _.max(res.map(e=>e.r-e.l));

}

提出

Issue

searchMinがverifyできていない

様々な問題への対応

参考リンク