titiaのノート: yukicoder contest 聖光学院プログラミングコンテスト2026 day2

2026年5月6日水曜日

　A一完で睡魔に襲われ撤退。

No.3527 Minimum Abs Sum

　解説AC。

　最初はCHT（slope trick）に見え、その後も、係数が一番大きいところなどと考えて失敗。

　係数が全て1のときの解法は知っていたし、

・abs(a*x+b)=a*abs(x+b/a)

　という式変形も見たことがあったはず。

　それにもかかわらず解けなかったのは反省。

　自力AC。

　総xorが打ち消し合うというのはどこかで見たことあったと思う。

　自力ACしたが非常に苦労した。

　サイクルに分解して何かするのだろう、というのは分かるが、そこからが難しかった。

　まず、サイクル長が奇数の場合は、2pと互いに素なことを利用して、全てをiの位置へ持っていくことができる。

　サイクル長さが偶数の場合、一般にはできないが、一つを除いてiの位置に持っていくことが可能。（ここの実装が意外と大変！　かなり混乱した）

　さらに、同じサイクル長さのものが複数ある場合は、サイクルを二つ並べて偶数番目を一つ目のサイクル、奇数番目を二つ目のサイクル、のようにすることで、全てiの位置へもっていける。

　よって、iの位置へもっていけないものは各偶数サイクルについて高々一つなので、

2+4+...につき高々一つ。これは√n未満という条件を満たしている。

　これは公式解説通りだったのだが、難しいし実装も大変だった。