小課題1

愚直にシミュレーションをすることで解けます。実は、\(K\) の最小値が存在する場合、\(K\) の上限が \(2M\) で抑えられることが示せるので、この問題を \(O(NMQ)\) で解くことができました。

共通の考察

操作によるアリ同士の位置関係は不変なので、アリ同士の位置関係が逆転している場合答えは \(-1\) となります。逆に、そうでない場合、アリがいる位置の多重集合さえ一致していればよいとわかります。

ところで、アリがぶつからずにそのまま進むとした場合でも、この多重集合に変化はありません。よって、今後はアリがぶつからずに進んだ場合、アリのいる位置の多重集合が一致するか、という問題を考えます。

小課題2

まず、アリ同士の位置関係については、ソートして矛盾がないかを確認すれば良いです。

アリ \(1\) について、そのアリが \(K\) 秒後にいる位置を固定します。また、\(K\) 秒後のアリの向きも固定します。これは、\(O(N)\) 通りしかありません。ここで、先ほどの考察より、\(K\) として考えられるものは一意に定まります。よって、\(K\) の候補を \(O(N)\) 通りに絞れたのでこの問題を \(O(N^2Q)\) で解くことができました。

小課題3

全てのアリが最初同じ方向を向いていることから、以下の事実がわかります。

任意の時刻 \(K\) について、最初の時点で一番左か一番右にいるアリのうちいずれか一方は、\(K\) 秒後において一番左か一番右にいる。

さらに、向きを固定することで、\(K\) として考えられるものは \(8\) 通りに絞れます。よって、この問題を \(O(QN\log N)\) で解くことができました。

小課題4,5,6

まず、位置関係がおかしい場合を排除します。これは、各 \(i\) について、\(i\) を左端としたときに位置関係で矛盾が生じるような最小の右端 \(j\) を求めればよく、これはセグメント木などを適切に用いることによって解くことができます。小課題 \(4\) については、位置関係を簡単に求められるので、これをせずとも解くことができます。

\(O(N)\) 個の時刻について、ある区間のアリがいる位置の集合が一致しているか、という問題を高速に処理するのが問題です。 今、多重集合 \(S\) について、\(S\) のハッシュを、\(S\) に属するすべての要素 \(s\) に対する \(c^s\) の和を \(P\) で割った余りとします。ここで、\(P\) は十分大きい素数とします。衝突確率の問題が生じますが、衝突確率は Schwartz - Zippel lemma を適切に用いることで \(M/P\) 程度で抑えられます(hash 関数が \(c\) に関して \(O(M)\) 次の多項式になることから従います)。よって、\(P\) を十分大きく(\(10^{18}\) 程度) 取れば良いです。

今、配列 \(X,Y\) を用意して、\(i\) 匹目のアリが時刻 \(t\) で右を向いているとき \(X_i = c^{A_i}\) 、そうでないとき \(X_i=0\) として、\(i\) 匹目のアリが時刻 \(t\) で左を向いているとき \(Y_i = c^{M-A_i}\) 、そうでないとき \(Y_i=0\) とします。時刻を昇順に見れば、\(X,Y\) の値の変化は \(O(N)\) 回です。また、時刻 \(t\) における区間のハッシュも、\(X,Y\) の区間和に、\(c\) や \(c^{-1}\) のべき乗を適切にかけることで求めることができます。

結論として、時刻の昇順に、\(X,Y\) をBITで管理して、各クエリについて多重集合の hash が一致しているかを判定すれば良いです。計算量は前計算の部分を除くと \(O((Q+N) \log N + Q\log P)\) となって、hash が衝突する確率も十分小さいことが示せるので、この問題を解くことができました。具体的には、\(M/P\) は\(10^{-12}\) で上から抑えられ、テストケース全体のクエリ回数が \(400000 \times 100 = 4 \times 10^7\) 回ほどなので、\((1-10^{-12})^{{10}^8} \fallingdotseq 1-{10^{-4}}\) ほどになり、運があまりにも悪くなければ通ると考えます。

定数倍の差で落ちた場合、\(X,Y\) の差分を持つと BIT の本数が減ります。また、Sparse Table なども適切に活用することによって、定数倍が改善すると考えられます。