Codeforces Round #574 - E. OpenStreetMap - Senの競技プログラミング備忘録

概要

n行m列の行列がある。それからa行b列の部分行列を切り出す。(n-a+1) * (m-b+1)個できる。部分行列の項の最小値の和を(n-a+1)*(m-b+1)個分足した値を答えよ。
ただし、n行m列の行列は $a_{ij}=g_{i*(n-1)+j}$ として、 $g_{i*(n-1)+j}=(g_{i*(n-1)+j-1} * x + y) (mod z)$ である。

制約: 1 <= a <= n <= 3000, 1 <= b <= m <= 3000, 0 <= x, y, z <= 10^9

ACするまで

1. 与式で構築された行列、数学的な規則を利用して解くのはなさそう。
2. 典型を感じる。2次元セグメント木でいけそう(後述)
3. 1次元ならば、サイズ固定なのでスライド最小値で行けそう。でも2次元。。。
4. よく考えてみたらスライド最小値は軸ごとに独立。2回やればいいので終わり->AC!

考察

f:id:Sen_comp:20191227222011j:plain

このスライド最小値というテクニック、蟻本にもある。(上級編)公式解説の貼ってあるページはスライド最小値の紹介。

このスライド○○シリーズはおそらくモノイドならばすべてできると思う。(調べます)

ACソースコード：

Submission #67664506 - Codeforces

2Dセグメント木

2次元セグメント木といって、サイズ可変の区間取得がO(logH log W)、1点更新もO(logH logW)のデータ構造がある。これでも今回の問題は理論上解くことができるが、僕が投げてみたところ、TLEではなくMLEしてしまった。3000 * 3000の配列の実質4倍確保するアルゴリズムなので、メモリ関連が意外に厳しかった。

MLEソースコード：

Submission #67684983 - Codeforces

一言

There is almost nothing to say about this problem. It is pretty standard data structure problem.
これを解けないのは俺が悪い。