[テストケース案] Min Plus Convolution (Convex and Arbitrary)

[NachiaVivias]

今のテストケースのうち small_07 ( $N=3,M=2$ ) のみで WA になるような誤りを含んだソースコードを提出しました。 : 185908

ミスは、再帰をやめる条件がを「 1 列まで reduce された」にしていることで、その後では 1 行まで reduce されたことを想定して実装しています。

試したうちでは、次のケース( verifier を通しました)でも出力が誤っていました。

17 8
1 1 2 4 7 11 16 22 29 37 46 56 67 79 92 106 121
100000 100000 100000 100000 
100000 100000 100000 2

誤：
100001 100001 100001 100001 100001 100001 100001 3 3 4 6 9 13 18 24 100106 39 48 58 69 81 94 108 123
正：
100001 100001 100001 100001 100001 100001 100001 3 3 4 6 9 13 18 24 31 39 48 58 69 81 94 108 123

$b$ の 2 の位置がこれ以外だとおそらく正しく計算されます。

---

以下の内容でテストケースを提案します。

• 比 N/M が大きい　特に M=1 を含む
• 比 N/M が小さい　特に N=1 を含む
• 端の 1 要素だけ極めて小さい値である（早い段階で 1 列まで reduce される可能性がある）