AGC-003 - blogskol

A-Wanna go back home

setとかで

B - Simplified mahjong

一番小さいやつから見ていくとなるべく一個大きいやつとペアを組んで挙げたくなる
ただ自身も2個単位での消費が出来るので奇数個だけ残すようにはしない

C - BBuBBBlesort!

3個での交換だと偶奇が変わらないから偶奇が完成形と異なるやつらには絶対二つでのswapが必要
逆にそれ以外では偶奇ごとに分ければ任意のswapが可能なことから好きな様に並び替えられるのは明らか

D - Anticube

まず $P^3$ の形の約数は全部割るべきで、これは $10^3$ くらいまでの素数を見ればいい
そうすると、自分とペアで立方数になる可能性のある数は一意に決まるので、mapで各値が何個あるかをメモしておけば、
- ペアで立方数になるのがないならそのままansに加算
- あるなら多い方だけをansに加算
すればいい
そこで、各値ごとに自身とペアで立方数になるのがあるかを探す
これは同じ様に $10^3$ くらいまでの素数で見てあげるだけじゃダメで、さらに $10^3 〜 10^5$ くらいの素数も見ないといけない
でも既に $10^3$ までの素数では割って挙げていれば
1. $10^3 〜 10^6$ （この時必ず素数）
2. $10^4 〜 10^5$ の素数の二乗
3.その他（ $10^3$ 以上の異なる素数の積や $10^6$ 以上の素数など）
この3パターンしか可能性はなく、1かどうかの判定は簡単、3だった場合は必ず立方数になるペアがないから、2かどうかを判定出来ればいい
これはsqrtを取ってから二乗して元に戻るかで判定できる

E - Sequential operations on Sequence

解説AC
クエリを単調増加にしてあげていいのは明らか
とにかく同じ数列が何回もループして出てくるのでそれをなるべく綺麗にまとめてあげる必要がある
$(K)$ で $1,2,...,K$ という数列を表すことにすると、
例えば、1回目のクエリでは（ $q_1$ が $N$ より大きいとして）、 $(N)$ が $\lfloor \frac{q_1}{N} \rfloor$ 回繰り返された後 $(q_1$ %[N)]が継ぎ足される
$i$ 回目のクエリでは、 $i-1$ 回目の数列を[tex:\lfloor \frac{q_i}{q{i-1}} \rfloor]回繰り返したあと $q_i$ ％[tex:q{i-1}]分だけ継ぎ足される
継ぎ足しは $q_{i-2}$ に対しての操作と見て再帰的に考えてやることが出来て、最終的に $q_1$ までを繰り返した後余った分は $(K)$ と言う形で末尾に追加される
これをさらに注目すると、 $i$ 回目のクエリでは $(K)$ と言う形の数列はたくさん登場するけど、新しい $K$ は最後にたかだか一回登場するだけと言うことが分かる（説明が下手だね、(A)(B)(A)(A)(B)(A)(A)(B)(K)みたいな形で、クエリが終わるごとに数列は増えるんだけど末尾のK以外のAとかBとかは既に $i-1$ 回目までのクエリで登場している数字だってことが言いたいんだけど）
なので「 $i$ 回目のクエリが終わった直後の数列の状態が最終的に何回繰り返されるか」を表す配列Aを持ち、クエリを後ろから見ながらAを作っていく＋末尾に追加する $K$ の長さを把握してansの $1〜K$ に $A_i$ 加算してやることで答えを得ることが出来る
加算部分は実際にはimos法を使うことでまとめて出来る
このままだとクエリを後ろから見る際に、各クエリごとに自分より小さいクエリ全部を舐める必要があるので $O(Q^2)$ かかるように思えるが、実際は継ぎ足し分が $q_j$ より小さい場合は継ぎ足し分に対してなんの操作も起きないことと、 $q_j$ の方が小さい場合には $q_j$ であまりを取るため継ぎ足し分が半分以下になることから、操作は $\log q_i$ 回しか起こらないことがわかり、どこで操作が起きるかを二分探索で探してやれば $\log q_i \log Q$ で一回のクエリを終えられるため、全体で $Q \log q \log Q$ で計算が終わる