yukicoder contest 492

　A一完。Bを考えているとき睡魔に襲われてしまった。

No.3441 Sort Permutation 2

　自力AC。

　index x→P[x]に辺を張り連結成分ごとに分解した後、その差のgcdがxなら、xの約数たちには連結成分-1をプラスする。

　と、これが必要条件なのはコンテスト中に分かっていたが、それ以外にも答が増えることはありそうに思い、たとえば、「3 4 2 1」のとき2を使わないようにできるか？　と考えていた。

　コンテスト後に実験してみると、結構簡単に使わずにソートできたので、上で書いた必要条件が十分性を満たしそう、と思って提出したらAC。

　なお、これだけで良いことは、公式解説を開いても「帰納法などで証明可能」としか書いていなかった。現在も証明方針が分かっていないが、やろうとすれば自力で証明できるのだろうか（やる気はない）。