エクサウィザーズ 2019：C - Snuke the Wizard
問題
解法
答えとして知りたいのは，各ゴーレムがどこのマスにいるかではなく，マスから落ちるかどうか．また，各ゴーレムが最初の位置関係から逆転することはない（一緒の位置になることはある）．これを踏まえると，左のマスから落ちるゴーレムと右のマスから落ちるゴーレムの最初の位置を知ることが出来れば，最初の段階でその 2 つのゴーレムの間にいるゴーレムはマスから落ちないことが分かる．この境界となる 2 つのゴーレムは二分探索をすることで求められる．二分探索の中であるゴーレムが左・右に落ちるかどうかの判定は愚直に O(Q) かけることが出来るので，全体で O(QlogN) となる．
解答
コンテスト中に解けなかった．
