今回はリールの長さ及び登場する絵柄の種類が10と固定されていますが、これを$m$とします。
これを以下の2つの解き方で解きます。
- 1: 解けるまでの時間を愚直に総当たりする解法 O(n^2m^2))
- 1-2: 1を少し工夫した解法O(nm^2)
- 2: 解説通りの解法 O(max(nm, m^2))
1: 解けるまでの時間を愚直に総当たりする解法 O(n^2m^2)
本問題の条件では、揃える文字$x$を決めたとき、$n$本のリールそれぞれを使ったかを覚えておくことで以下のように解くことができます。
- STEP1: 今の時間をcurtimeとする。この時、各リールのindexが
curtime % 10の位置の文字が使える(curtimeでボタンを押すと、その数値が表示される) - STEP2: 使っていない各リールを見ていき、使えるリールがあるなら使う(使えるリールが複数あった場合、どのリールを使っても結果は変わりません)
- STEP3: すべてのリールを使い終わったらその瞬間のcurtimeがその数をそろえる最小時間
この時の計算量を考えます。今、$x$ですべてのリールを揃えたいとすると、あるリールを使った次にほかのリールで$x$が揃えられる最悪のケースは、入力例2のようにすべてのリールが同じだと$m$回時間進まなければ使えません。各リール$n$本に対して各時間で確認するので、次の使えるリールを探すのに最悪$nm$の時間がかかります。すべてのリール$n$本を揃えないといけないので、$O(n^2m)$で$x$をそろえるときの時間が求められます。
これを、揃える文字$x$を$m$種類に対して処理するため、全体の計算量は$O(n^2m^2)$です。
1-2: 1を少し工夫する O(nm^2)
さて、1はSTEP2が工夫できます。使えるリールが複数あった場合、どのリールを使っても結果は変わらないので、最初から数$x$を選んだ時に各indexで使えるリールの本数を覚えておけば良いです。これによって使えるリールがあるかを判定する必要はなくなります。
この時の計算量は、各リール$n$本に対して各時間で確認するが不要になるので$O(nm^2)$です。
2: 解説通りの解法 O(max(nm, m^2))
解説通りです。ある数$x$を揃えたいとき、全リールのindexに$x$が存在する個数をcnt[index]とします。indexに$x$がある1つ目のリールをそろえるには時刻$index$で揃えられます。そのような2つ目のリールを揃えられるのは時刻$m$後なので$index + 1 \times m$です。そのindexに$x$があるリール全てをそろえるのには、時刻$index + (cnt[index]-1) \times m$です。各indexについてこの時刻を計算し、そのmaxが$x$を揃えるのにかかる最小の時間です。これをすべての$x$について試行すればいいです。
事前に$O(nm)$でcntを計算したあと、$m$個の数字についてindexが0から$m$まで調べれば良いです。$O(max(nm, m^2))$ です。