yukicoder No.1036 Make One With GCD 2 に追加したケースについて

追記

4/25 Sparse Tableを落とすケースが追加されてたので記述を修正

 概要

 yukicoder上で出題されたこの問題にHackケースを追加しました. (99_challenge01.txtというケースれふ)

 いくつかある解法のうち, セグメント木上での二分探索を行う解法に対する悪意的な入力なのれふが, 何故落ちるのかが分かりづらいようなので記事化することにしました.

GCDの計算ステップ数について 

 GCD(a,b)の時間計算量がO(log(min(a,b)))であることは皆さんご存知のことと思いまふ.
 しかし,  それ以上の理解としてGCD関数の挙動をよく眺めると, GCD関数が実際に行う計算ステップ数はmin(a,b)の値を剰余算によって小さくした回数である, ということが分かりまふ.

 このことを考慮すると, 次のことがいえまふ.

セグメント木にGCD(A_l,A_{l+1},...,A_r)の値を取得するクエリを投げた時,
その計算量はO(logN+logA)(O(logNlogA)ではない)

 区間GCDの計算にあたり, logN個程度の区間をマージすることになりまふが, この過程で発生する「min(a,b)の値を剰余算によって小さくする回数」は全体でlogA回程度であって, logNの係数ではないためれふ.

 今回の問題に対する種々の解法の計算量について

 まず, セグメント木で区間GCDを取得可能にし, l=1,2,...に対しrを二分探索する解法がありまふが, この計算量は上で説明した通りO(NlogN(logN+logA)になりまふ.
 この解法は基本的にTLEになるようれふ.(ケースを追加するまでもなく落ちてました)

 続いて, 二分探索の代わりに尺取り法を用いる解法がありまふ. これはO(N(logN+logA))であり, 高速れふ.

 問題なのは, 「セグ木上の二分探索」と呼ばれるテクニックによる解法や, Disjoint Sparse Tableを用いて区間GCDを取得して二分探索する解法れふ.
これらは基本的に高速れふが, その気になればO(NlogNlogA)となるようなケースを作れまふ.
 そして一方, Disjoint Sparse Tableの代わりにSparse Tableを用いた場合, 落ちるケースを作るのが難しいれふ(というより, 存在するか怪しいと思ってまふ).

どのようなケースで落ちるのか

 (a,b)をGCD(a,b)の計算ステップ数が大きくなるような(a,b)の組としまふ. (これは, 互除法の逆操作を考えるとフィボナッチ数列の隣接2要素を選ぶと良いれふ)

 結論からいうと, 最悪ケースはこのaとbを交互に1024個ずつ並べたケースれふ.(個数は2べきでほどほどに大きければ基本なんでも良くて, もう少し妥当なのがあるかもしれません)

 「セグメント木上の二分探索」と称されるアルゴリズムでは, 現在のノードが条件を満たす場合は右や上に, 満たさない場合は下に移動しまふ. 今回の問題における条件は「GCDが1より大きいこと」れふ.

 提示した最悪ケースにおいては, 同じ要素がある程度連続しているため, それらのみを含む区間においては条件を満たすものとしてある程度上や右に移動しまふ. そして, 条件を満たさなくなってからは, GCDが1になるようなrの境界が2べきの位置に存在しているため, 下のほうにあるノードまで移動することで探索が終了することが多いれふ.  ここで, 条件を満たさない場合に行われるGCDの計算ステップ数は, ある程度の深さより下においてlogA回となりまふ. これは, マージ元の値が上述のaで, マージされる値がb(あるいはその逆)となるためれふ.

 このことから, 結局, セグメント木上で二分探索を行った場合, logNに比例する回数だけO(logA)の計算が行われることになり, TLEとなりまふ.
また, これは意図していなかったのれふが, Disjoint Sparse Tableも同様に落ちるようれふ.

 一方, Sparse Tableを用いて二分探索をする解法はこのケースのようなアプローチで最悪ケースを作るのは難しいれふ. Sparse Tableにおける区間クエリでは, 前計算済の区間2つがマージされまふ. ここで, 左側の区間におけるGCDをx, 右側の区間におけるGCDをy, 共通する区間におけるGCDをzとすると, マージの計算ステップ数がlogAに比例するためには, たとえばx=a, y=b, z=abが満たされなければなりません. しかし, 二分探索によってほとんど無作為に近い形で選ばれる区間たちすべてに対してこれを満たすような数列を構築できる気がしないため, 実際にはO(NlogN)程度で動作するのでは?と思ってまふ. (証明等をしたわけではありません)

 ほとんどの要素をabにし, 1024個に一つa・bを交互に混ぜることで条件を満たす数列が構築出来たようれふ. (そのような類のケースが追加されていました)
https://yukicoder.me/submissions/470831

このケースへの対処法

セグ木上での二分探索解法を採用しない

 はい

数列をずらす

 セグ木のノードが同じ要素で埋まった場合に計算量が悪化するため, 数列の先頭にダミーの要素を挿入すると取り敢えず今回追加したケースにおいてはTLEしなくなりまふ.
フルフィードバック形式のコンテストにおいてはこれをするだけでコードを見ない限り落とせなくなりまふし, Hackのあるコンテストにおいても追加されるダミーの要素をランダムに決めるとHackは困難になりまふ. (が, 運悪くシステス等で落ちる確率はそれなりにありまふ)

 一応表明しておくと, この問題に関して, 要素を挿入することでTLEを回避したコードを追いかけて対応するHackケースを追加するようなことをするつもりは(私は)ありません.

余談

 もしかすると, 数列をずらす程度じゃ対処できないHackケースが存在するかもしれません. (存在しないことを示してないので)