AtCoder Beginner Contest 199（Sponsored by Panasonic）参加記（～C問題）

早解きしかできなかった
f:id:mmnkblog:20210424224915p:plain

A - Square Inequality

こういう、一見そのまま解くだけに見える問題を素直に実装すると、たいてい何らかの罠にはまる。たとえば、

愚直に計算すると実行時間制限に間に合わない
計算途中でオーバーフローする
割り算や平方根の計算時に小数の誤差が発生する
コーナーケースが存在する（0除算など）

などが考えられる。今回は上記のどれにも当てはまらないので、単純に不等式評価を行うだけ。A問題なのでこれでACできる。
計算量は $O(1)$ 。

B - Intersection

解 $x$ の候補の最小値は $A_{\min}$ 、最大値は $B_{\max}$ であるので、解 $x$ を全探索して条件を満たすかどうか全探索してカウントする。
計算量は $O(N B_{\max})$ 。

ちなみに、別解が存在する。条件式より、解 $x$ の範囲は $A_{\max}\le x \le B_{\min}$ となる。逆に、この範囲にある整数 $x$ はすべて条件を満たすので、答えは $B_{\min} - A_{\max} + 1$ となる。
こちらの計算量は $O(N)$ で、はじめの解法より高速。

これは、先ほど挙げた罠のうち、「愚直に計算すると実行時間制限に間に合わない」問題。というか競プロの問題の９割がこれである。
クエリの数が最大で $3\times 10^5$ 個あるため、各クエリに対して高速に回答する必要がある。
クエリ $1$ では、文字を交換するだけなので、計算量は $O(1)$ である。
クエリ $2$ では、長さ $N$ の文字列を交換するので、計算量は $O(N)$ である。
なので例えば、すべてのクエリがクエリ $2$ だった場合などを考えると、愚直な解法の計算量は $O(NQ)$ となってしまいTLEする。

ところで、クエリ $2$ を偶数回連続で処理すると元の文字列に戻る。連続で処理しなくても、クエリ $1$ で操作されなかった文字 $S_i$ に関しては、クエリ $2$ が偶数回処理されれば元の位置 $i$ に、奇数回処理されれば位置 $(i+N)\bmod {2N}$ に移動することがわかる。さらに、クエリ $2$ を奇数回処理したあとにクエリ $1$ を処理するのは、クエリ $2$ での反転を一度無視して、クエリ $1$ で与えられた値 $A, B$ に対して文字 $S_{(A+N)\bmod {2N}}, S_{(B+N)\bmod {2N}}$ を交換した後にクエリ $2$ を処理するのと同じである。
つまり、クエリ $2$ は最後に一度だけ処理すればよく、クエリ $1$ を処理する時点での「本来何回クエリ $2$ を処理しているか」がわかれば、全体として $O(N+Q)$ の計算量で全てのクエリを処理できる。