Daily Cumulative Totalizer

 累積中間和付きトータライザで、前述の実装概念図です。

仕様として入力するのは、Day毎の累積和です。通常のトータライザ仕様は、一番上の黄色で示した終点での[min:max]しかありません。

が、Daily Cumulative Totalizerは、Reduceしたグラフから得たDay毎の累積和を入力とするところが違います。

トータライザは、全体入力を再帰的に2分割していくトップダウンでUnaryCounterの合成は、ボトムアップで行われます。このとき、Daily累計和が与えられれば、分割したセグメントのSpecは、以下で生成することが出来ます。

pair<int, int> segmentTotalRange(int l, int r, const vector<short_range>& constraints) {

int mn_prev = (l == 0) ? 0 : constraints[l - 1].mn;

int mx_prev = (l == 0) ? 0 : constraints[l - 1].mx;

int mn_r = constraints[r].mn;

int mx_r = constraints[r].mx;

int L = mn_r - mx_prev;

int U = mx_r - mn_prev;

if (L < 0) L = 0;

int len = r - l + 1;

if (U > len) U = len;

if (L > U) return { 1, 0 }; // 不可能区間

return { L, U };

}

このようにして、きめ細かく制約することによりPathを出来る限り限定することが出来ます。トータライザの段数は、変わりませんが、通常のトータライザが、分割したセグメントでもトップ段のmax値でしか制約できないのに対し、累計中間和での[min:max]で制約するので、結果的にノード数合計も抑制されるものと期待できます。