A - Replace C or Swap AB

Hint 1

まずは C がない場合の問題について考えましょう．この場合の操作 (3) は，例えば A だけに注目して「A をひとつ右に動かす」というように考えると分かりやすいです．

Hint 2

次に C の扱いについて考えます．操作によって新たな C が作られることはないことに注意すると，$Y$ が C を含まない場合に帰着できます．その場合には，どの C を A, B にするべきかを貪欲に定めることができます．

解説 → https://atcoder.jp/contests/arc166/editorial/7182

---

B - Make Multiples

Hint 1

解説では「動的計画法を用いる」，「操作対象とする項の候補を絞って全探索する」という 2 つの解法を紹介しています．

解説 → https://atcoder.jp/contests/arc166/editorial/7183

---

C - LU / RD Marking

Hint 1

グリッドの辺全体を独立に扱えるいくつかの部分集合に分割しましょう．

Hint 2

答の計算に $O(H+W)$ 時間かかりそうな計算式が出てきますが，適切な事前計算によりテストケースあたりの計算を高速にできます．

解説 → https://atcoder.jp/contests/arc166/editorial/7184

---

D - Interval Counts

Hint 1

区間はある点集合を被覆するもののうちでなるべく大きなものを選ぶとしてよいです．すると，$L_j$ は $x_i+1$，$R_j$ は $x_i-1$ などの値に限定できます．

Hint 2

各 $i$ に対して，$L_j=x_i+1$ となる $j$ の個数や $R_j=x_{i}-1$ を満たす $j$ の個数を下から評価できます．そこから作った最小個数の区間による解の構成が最適であることが証明できます．

解説 → https://atcoder.jp/contests/arc166/editorial/7185

---

E - Fizz Buzz Difference

Hint 1

良い組のうち極大なものだけを考えればよいです．このとき，$L-1$, $R+1$ は $a$ の倍数であることが証明できます．

Hint 2

$L=al+1, R=ar-1$ と書ける場合について考えます．この区間に含まれる $b$ の倍数の個数は，$(al\bmod b)$ から計算できます．$r-l$ を固定したときに $b$ の倍数の個数が最大化されるのは $(al\bmod b)=b-\gcd(a,b)$ の場合です．

Hint 3

「$a,b,c$ が与えられるので，$(ax\bmod b)\geq c$ となる最小の $x$ を求めよ」というタイプの問題に帰着されます．これは $O(\log b)$ 時間で解くことができます．

解説 → https://atcoder.jp/contests/arc166/editorial/7186

---

F - Tangent Addition Formula

Hint 1

$t(x)=\tan(x)$ の満たす等式が題材となっています．$\tan(x)$ との類似を意識することで，考察がしやすくなります．

Hint 2

複素指数関数を用いれば，$\tan(x) = i\cdot\frac{1-r^x}{1+r^x}$ となる $i, r$ が存在することが分かります． 本問の $t(x)$ についても，（いくつかの例外を除き）$t(x) = i\cdot\frac{1-r^x}{1+r^x}$ のような表示を持つことを示していきましょう．

Hint 3

$p\equiv 1\pmod{4}$ の場合には $i^2=-1$ を満たす数 $i$ をとって，$t(x) = i\cdot \frac{1-r^x}{1+r^x}$ という式を考えることで解くことができます．一方で $p\equiv 3\pmod{4}$ の場合には，$i^2=-1$ となる $i\in \mathbb{F}_p$ を考えることはできません．しかし，（実関数 $\tan(x)$ が複素数を用いて表せるように）$i^2=-1$ を満たす新たな $i$ を付け加えて考察することで，$p\equiv 1\pmod{4}$ の場合と同様に解くことができます．

解説 → https://atcoder.jp/contests/arc166/editorial/7187