今回は ABCDEF の 6 完(72:45 + 10:00)(2TLE).
ABCD までは順調だったが、 E を誤読して F にいってから E を解いた。 でも精神状態は前よりかは悪くないと思う。
S.back() = '4' をするとよい。
3 重ループを回す。
頭の方を back にした vector を用意して、移動するごとに頭が移動した座標を push_back していく。 すると、vector の添字を 0-indexed だとすると、現在の vector のサイズを $s$ とすると、 $s-p$ 番目の位置にパーツ $p$ の座標が出てくる。
実装が面倒くさい。うまいこと座標を回転させて実装した。
最初、同じ値でも得点が増えると思ってしまったせいで、とんでもない問題だと思って次の問題に行ったが、 よく見たら種類数だった。ということは強連結成分分解をしてから DAG 上で DP するだけなので解ける。
値を使いまわすところを適切に決めてあげれば求めなければいけない状態数は $O(N \sqrt{N})$ 程度になりそうだということがわかった (解いてた当初は $O(N \log N)$ だと思ってたのですが違いました。訂正しました)。
まず、DP の計算式は、 $$ \mathrm{dp}[u] = \sum_{x, x > 0, u+A_u \times x \leq N} \mathrm{dp}[u+A_u \times x] $$ になるので、 どうにかこれを、 $$ \mathrm{dp}[u] = \mathrm{sum}[u+A_u][A_u] + 1 $$ $$ \mathrm{sum}[u][a] = \mathrm{dp}[u] + \mathrm{sum}[u+a][a] $$ のように変換できればいいなとなった。 dp を右から求める過程で $\mathrm{sum}$ を再帰で参照していく感じ。
sum をメモ化再帰で求めると、確かに状態数は $O(N \sqrt{N})$ 程度にはなりそうだが、そもそも map みたいなデータ構造に $10^8$ 個程度もデータが入ったら TLE してしまう。 時間計算量を見ると $O(N \sqrt{N} \log N)$ になっているし間に合うはずがない。 これで 2 TLE した。 だが、少し気づくと、 $a = A_u$ のとき、 メモ化のデータが求まっていることになるのだが、このときの $\mathrm{sum}[u][a]$ の値は実は $\mathrm{dp}[u] \times 2 - 1$ になっている。 さっきの $\mathrm{sum}[u][a]$ の式は $$\mathrm{sum}[u][a] = \mathrm{dp}[u] + \mathrm{sum}[u+a][a] $$ だが、 $a = A_u$ であるので、 $$ = \mathrm{dp}[u] + \mathrm{sum}[u+A_u][A_u] = \mathrm{dp}[u] + \mathrm{dp}[u] - 1 = \mathrm{dp}[u] \times 2 - 1 $$ となるわけである。 このようにメモ化をせず、 $a = A_u$ のときにこの式により計算を打ち切ってあげると $O(N \sqrt{N})$ で処理できることがわかって 特に重い計算もない(再帰は重いかもしれないが)ので TLE せずに解くことができる。
今もう一回解いたが、メモ化再帰せずに簡単に書けることがわかった。
これだけで書ける。
あと、$O(N \sqrt{N})$ の理由は、$A_i=1$ のものを $1$ つ、 $A_i=2$ のものを $2$ つと入れる余裕があるので すべてかぶらないように $A$ を構成するような最大ケースを考えると $O(\sqrt{N})$ 個程度の $A$ の種類数になるから と思っていたが、ただそのようなケースは実際には実在しないので、もう少し小さく抑えられるかもしれない。
おそらくであるが、 $P$ の原始根を求めて、それがループになっているので、 それぞれの値がどのような包含関係になっているかを計算できれば嬉しそう。 原始根の計算が早ければだが・・・
Perf=1997 だった。 最近はちゃんと 6 完できるようになっていっているので、パフォーマンスが安定しているが、 あまり爆発力もないという感じ。 やっぱり EF の解く時間が遅い。何だろうなぁ。 実質時間をかけたのは F だったが、式変形系は苦手なのかなぁ。 なんか今回は F が $\sqrt{200000}$ で分けるといいというテクニックだったみたいだから、 こういう考えを持てれば嬉しいが・・・
(2024/01/06 23:29)D, E, F をもう一度解き、G を解いた。
D は範囲外に出そうになるあるいは既に番号を振った場所につく場合に時計回りに回転するという実装を してみた。こっちのほうが実装しやすいと思う。
E だが、同じ整数で連結されているものを完全に同一視して計算することで dp を求めることができる。 具体的には、Unionfind でそれを連結して、代表元のみにアクセスするようにするという方法が挙げられる。 こうすることで整数が同じもの同士の辺については考慮しないようにできるので、 グラフが DAG になり、DP を計算することができるようになる。
DP の値のまとめ方を代表元に設定するやり方は面白いと思った。
$A_i > \sqrt{N}$ であるような $i$ については、愚直に計算しても $O(\sqrt{N})$ であるので そこは愚直に計算する。あとは $A_i \leq \sqrt{N}$ の部分だが、 これは上の説明で書いたような累積和を持とうとすると map などを使わずに普通に持つことができるので これも全体で計算量を $O(N \sqrt{N})$ にすることができ、 全体で計算量は $O(N \sqrt{N})$ であることがわかる。
この解法も十分に速いし、思いつくならこっちを思いつくほうが考察時間を短縮できると思う。
考え自体はかなり惜しいところまで行っていたみたいだった。 位数を求める、というところは考えがいっていたのだが、少し調べてたら、 ある位数がある位数の約数になっていると条件を満たすという ことが書かれていて、本当にそうなっていてやばいと思った。
おそらく考え方はこうである。原始根をまず探して、その $0$ 乗から $P-2$ 乗までを列挙することを考える。 すると、$1$ から $P-1$ までの値は全てでてくるわけである。このときにそれぞれの値の遷移する状況を考えると、 位数が同じものはすべて同じサイクルの中に入るということがわかる。$i$ の位数を $B_i$ と置いてみると、 $\frac{B_i}{P-1}$ の間隔で値が埋まっていく状況になる。 ということは、その倍数の間隔で値が埋まるものについてもそれが包含されていると言える。
これを $B_i$ の方で考えると、$B_j$ が $B_i$ の約数になっていれば ${A_i}^k \equiv A_j \pmod{P}$ の条件を 満たすことがいえるのである。
ということは、逆に考えて、 $B_i$ が $B_j$ の倍数になっているものを探すことで今回の問題を解くことができる。 この探し方は $B$ の値の種類が $P-1$ の約数の個数しかなく、 同じ値のものは一斉に計算できることから計算量を間に合わせることができる。
ここで問題なのが、$A_i$ の位数をどのように求めるかということだが、 最初、自分は $P-1$ の約数について全列挙し、仮に $d$ とすると、${A_i}^d \equiv 1 \pmod{P}$ を満たす最小の $d$ を 探すことで求めようと思ったが、約数の数というのは $P \leq 10^{13}$ の制約では意外に多く、 TLE してしまう。 これも少し盗み見して解法を知ってしまったのだが、ある $d$ で値が $1$ とでてくるならば、$d$ の倍数でも $1$ と出てくる わけなので、$P-1$ から素因数を割っていってどこまで割れるかを検証することで検証回数が $O(\log P)$ 程度で 収まるということがわかった。 すると、位数を求める計算が、 $O(N \log^2 P)$ くらい？になって、$P-1$ の約数の個数を $d_{P-1}$ と置いてみると、 $O(N \log^2 P + (d_{P-1})^2)$ くらいになるのかなと言う感じだった。
原始根の累乗の値の並びから見たときの性質について少し理解を深められて良かった。
(2024/01/07 18:50)