ABC194-E Mex Min の嘘解法

たまにはこういう記事があってもいいかなって

注意書き:
・「嘘解法」は定数倍高速化や強いデータ構造などで意図的に想定解法でない計算量を通したというわけではなく、
あまり証明などせず投げて通ったが、テストケースの緩さに甘えたという意味になります。
・つらつらと解いてる最中および振り返り中の思考を書いているだけなので、最終的に「TLEでした」というオチになります。
これ、もしかして嘘解法だったのではないか?というモヤモヤ解消のための自己満足であることをご了承ください。

問題概要

長さNの数列Aと整数Mが与えられる。
元の数列から取り出すことのできる長さMの連続部分列は N-M+1 通りあるが、そのすべてに対してMexを求めたときの最小値を求める。

制約

  • 1 <= M <= N <= 1.5 * 106
  • 0 <= A_i < N
  • 入力はすべて整数

atcoder.jp

とっかかり

固定長の連続部分列を順番に調べていくのは、イメージ的には長方形に穴が開いているフィルタ、もしくは窓を1マスずつスライドしていく感じを思い浮かべています。

1マスずらす前後で変わるのは先頭と末尾の二個だけなので、対応する数字の個数を1個増やしたり減らしたりするだけで最新の状態を把握できます。

(初期化処理として、1~M番目に含まれる要素数をカウントしておきます。ついでにその中のMexも調べる)

f:id:socha77:20210703042048p:plain

さて、ここでMexが変化する時というのはどういう場合があるのかを考えます。

具体的には

  • ある整数の個数が-1されて0個になった時
  • ある整数の個数が+1されて0個でなくなった時

が変化の可能性のある時です。



ある要素が0個になった時

もし現在のMexよりもその要素が小さいばあい、新しいMexになります。
「現在のMex」みたいな変数を書き換えるだけなので、O(1)で済みます。

f:id:socha77:20210703042655p:plain



ある要素が0個でなくなった時

それが現在のMexでない場合は影響なし。

もしも現在のMexが0該当要素の場合、即座にわかることはMexが変更になるということだけで、次のMexが何になるかはわかりません。
なので、数字を1ずつ大きくしていき今0個かどうかを調べる必要があります。

f:id:socha77:20210703043002p:plain

計算量を考える

(この辺りから嘘っぽい言動が混じり始めます。解説の類ではなく、コンテスト中の思考の追い直しということをご理解ください。)

とりあえず上記の流れで窓をスライドするごとのMexが分かる → 結果としてmin(Mex) が分かる

というところまで来ました。TLEになることを考えなければ解を得ることはできそうです。
ただ1ステップにつき O(M) の操作があると、最終的に O(N2) 辺りになってしまう気がするな~~

というわけで、時間のかかる方の走査についてもう少し考えを巡らせてみます。 すると、以下のようなひらめきを得ます。

f:id:socha77:20210703044202p:plain
この時点でもう嘘ついてたらごめんなさい

これ... もしかして償却計算量ってやつじゃないか?


戻るパターンの処理はO(1) だから

そんなに大きくなる感じはしないし (??)

ならしで最終的に処理回数がO(N) になるのでは!例えば2N回で抑えられるとか (????)


いや~ 面白い問題でしたね

提出 → AC (申し訳なし)

答え合わせ

もうツッコミを入れている方もいると思うのですが、
戻る処理はO(1) だからと言って数字1個分しか戻らないわけではなく、大きく戻ることもあります。

f:id:socha77:20210705010800p:plain

図のようにMexのシャトルランをひたすらさせられるような入力があれば、最悪ケースとして
[Mexの最大値] * [窓のスライド回数 / 2] 回程度の処理が必要になり計算量はO(N2)程度になってしまうと考えられます。


それでは最悪ケースを達成する入力を具体的に考えていきます。 Mexが 0, K, 0, K ... と続くような理論値のケースは思いつかなかったのですが、
Mexが 0, K, 1, K, 2, K, ... と続いていくようなパターンを発見しました。

最悪ケースの生成コードを作ったので、貼っておきます(ちょっと面倒になってきた。実際にどんな入力なのか気になる方は実行してみてください。)

    mex_max = 10  # ここで入力の大きさを調整
    a_as_inf = 1000000

    li = []
    for i in range(mex_max+1):
        li.append(i)
        li.append(a_as_inf)

    for i in range(mex_max+1):
        li.append(i)
        li.append(a_as_inf)

    window = mex_max * 2 + 1

    print(len(li), window)  # 入力のN, M
    print(*li)              # 入力のA_1 ... A_N

    # ↓ Mexを求める愚直解 小さいケースで試すこと
    # l = 0
    # while l + window <= len(li):
    #     arr = li[l:l+window]
    #     mex = 0
    #     while mex in arr:
    #         mex += 1
    #     print(mex)
    #     # print(arr)
    #     l += 1

mex_max = 10に設定して愚直解込みで実行すると、Mexが 11, 0, 11, 1, 11, 2, 11, 3 ... となるさまが見て取れるかと思います。

最悪ケースの生成が完了したため、実際にTLEするかどうかを確認します。 上の生成コードでmex_min = 370000
にすると
N = 1480004, M = 740001
となり最大ケースに近い形になります。

単純にACコードに食わせようとしたのですがコードテストの入力制限をオーバー、またローカルで実行しても単純に処理が返ってこないため 小さいケースで処理回数が O(N2) になっていることを確認する方向にします。

問題のACコードに「Mexを示すポインタを大きい方向に進めた数」(= シャトルランの図で前方向に進んだ距離の合計) を数える処理を仕込みました。

以下にそのコードを貼っています。(AC扱い)
Submission #23994824 - AtCoder Beginner Contest 194

結果

mex_maxが

  • 3700 => 処理回数: 6850551
  • 37000 => 処理回数: 684555501
  • 370000 => 帰ってこないのでパス

という感じで実測でもおおよそ (mex_max2) / 2 回程度の処理を回していることが確認できました

まとめ

なんの記事だったんだ?これ

この話をまとめる途中で結構回り道をしたのですが、結果としては納得しないまま放っておくの気持ち悪いな~~という思いをすっきりさせることができたのでまあよかったかなと思います。

(この記事の副題は「ACしたと思ったら嘘解法だと思ったら実は正しい解法だったと思ったらやっぱり嘘解法だった」という感じになっています。)

せっかくまとめたので、他の問題を解くときに何か流用できる部分があるといいな... と思っています。

それではここまでお読みいただきありがとうございました。