「時刻 \(T\) までに数字 \(D\) で揃えることはできるか」という判定問題を考えます。この問題を高速に解くことができれば、\(T\) について二分探索することで「数字 \(D\) で揃えるまで最小何秒かかるか」を求めることができそうです。

判定問題は、各リールに対して止める時刻を割り当てるマッチング問題だと思うことができます。各リールに対応する頂点と、各時刻に対応する頂点を \(2\) つの部集合とし、時刻 \(t\) にリール \(i\) に \(D\) が来るとき時刻 \(t\) とリール \(i\) の間に辺をはった二部グラフにおいて、リール側の頂点を全て使うようなマッチングが存在すれば答えはYesとなります。

例を挙げます。以下の入力の数字 \(1\) に対して構築されるグラフは次の通りです。左側の t から始まる頂点が時刻を、右側の r から始まる頂点がリールと対応します。（時刻 \(5\) まで）

3 4
1212
1233
3312

時刻の上限について考えます。どのリールも、そのリールにおける数字 \(D\) の \(N\) 度目の登場までに止めるとしてよいです…(★)。なぜなら、もしそうでないリールが存在したとき、そのリールの数字 \(D\) の \(N\) 度目の登場までに他のリールを止める時刻と重なっていないものが存在するため、そのような時刻の \(1\) つで止めるように変更しても損をしないためです。よって、数字 \(D\) で揃えることが可能ならば、時刻 \(NM\) までに達成可能です。

また★の事実から、リール側の頂点の次数は高々 \(N\) としてよいです。これによりマッチング問題における辺の個数は \(O(N^2)\) とすることができるため、（座標圧縮により時刻側の不要な頂点を削除したうえで）最大流を Dinic法などを用いて求めることで \(O(N^3)\) で判定問題を解くことができます。

よって数字の種類数を \(d\) として \(O(NM+N^3 d\log N)\) でこの問題を解けました。