[問題案] Matrix Argmin

[kmyk]

問題ID: matrix_argmin 問題名: Matrix Argmin

想定アルゴリズム: monotone minima (任意) 参考資料: {URL}

問題概要

monotone な H * W 行列 A が与えられる。 A の各行 y < H ごとに、その行における最小値の位置 argminx A{y,x} を求めよ。

入力

H W
A_{0,0} A_{0,1} ... A_{0,W-1}
...
A_{H-1,0} A_{H-1,1} ... A_{H-1,W-1}

出力

x_0
...
x_{H-1}

制約

• 1 <= H * W <= 10^6
• 0 <= A_{y,x} <= 10^9

検討すべき事項

• 問題名/IDはこれでよさそうか
• monotone の定義を、distinct な行列にのみ定義されるものにするか、一般の行列に定義するか
  • SMAWK との関係性などもあって一般的な方が好きです。でも distinct の方が問題文が簡潔だったりするし、あまりこだわらない
• 想定 O((H+W) log H) だけれど、入力 O(HW) なので愚直 O(HW) も通ってしまう。どうすればよいか
  • 選択肢は「入力 O(HW) を受け入れる」「monotone な行列の全体を入力とすることを諦めて O(HW) を回避する」「A{y,x} でなくて enc(A{y,x}) を入力して O(K) の dec(...) を計算させ、想定を O(K * (H+W) log H) にする」「リアクティブ機能を実装して質問回数で制限をかける」ぐらいかなと思う。特に意見はなく、admin にまかせたい

[yosupo06]

インタラクティブを今週末に実験してみます(いちいちflushとかする必要があるはずで、そもそもどのぐらいの速度が達成できるのか…)

[hotman78]

monoid が乗るデータ構造に対して monoid 全体を入力として与えていない事を考えると、 monotone/totally monotone/monge に関しても特殊化して与えてしまっても問題ないと思うのですがどうでしょうか。 具体的には、 f(i,j)=g(A_i-A_j)+B_i+B_j ( g は あまり大きくなりすぎない程度の多項式(CHT の区別を考えると 3乗（？）が良い？)) などがあると思います。

[hotman78]

と書いてから思ったんですが実は新機能の C++(Function) header を応用すれば（言語が限定されてしまいますが）インタラクティブ可能そうなので、それもありですかね。

[SSRS-cp]

通常のインタラクティブ (? i j を出力すると f(i,j) が入力される) を行うのは問題がありますか

[hotman78]

ジャッジが対応しているかどうかを気にしていたのですが、よく考えると checker.cpp をいじるだけで普通に使えそうな気もしてきました