Codeforces Round #628 (Div. 2)

　Dまでの四完でした。
　コンテスト中は、EやFはあまり考えずに寝てしまった……。

コンテストへのリンク
コンテスト後のツイート

E. Ehab's REAL Number Theory Problem

　解説AC。

　約数が7個以下ということで、

・素因数は高々二つ。

　に気付くのが重要。また、

・$x^2$を因数に持つとき、$A/x^2$を考えても同じなので、平方数を約数に持つならそれで割っておく。

　というのにも自力で気付けた。

　ここでグラフを考えるのはまあ自然だと思う。

　各A[i]を頂点とし、たとえば、6=2*3と、22=2*11のように、同じ素因数を持つもの同士に辺を繋ぐ。そして、最小のサイクルを検出すれば良い。

　……という方針は自分で思いついたのだけど、それだと難しいと思う。これでも上手くやれば解けるかもしれないが、サイクル検出を効率よくやるのが難しい。

　公式解説では、素数を頂点にし、6があれば2と3に辺を結ぶ。7があれば1と7を結ぶ……というにグラフを構成している。これでも同じく、最小サイクル検出問題に帰着できる。

　さて、最小サイクル検出は普通にやると、頂点数の二乗くらい（この問題では、辺の数も頂点数*2くらいで抑えられるので）の計算量がかかってしまう（と、公式解説にはあった。確かに各頂点ごとにBFSすればそれくらいでできるけど……もっと良い方法はないの？）。が、ここで、$A[i]\leq 10^6$に着目。$10^3$上以上の二つの頂点が結ばれることはないため、サイクルの端点は$10^3$以下として良いので、それらからBFSすれば良い。

　これをふまえると、計算量が大きく減らせる。

　これでACできるのだけど、実際はその後の実装にも苦戦してしまった。途中で座標圧縮したりしたらTLEが取れたけど、もっと良い実装があるはず。

F. Ehab's Last Theorem

　解説AC。

　ついでに、最近出た類題もAC。この類題の方が簡単なので、これを先にやってから取り組んだのは良かった。

　公式解説には、DFS木を使うものと、次数を考えるものの二通りが載っており、前者はじゅぴろさんの日本語の解説もあります。

　ただ、私は後半の、サイクルがなかったときの独立集合の取り方がよく分かってません……。

　なので、後者の方法でやりました。

　次数が少ない順（heapqで管理）に点を取ってきて、独立集合に付け加えていきます。

　ある点を使ったら、その点の近傍の点は使えず、さらにそこから繋がっている点の次数を一つ減らす……というようにやっていく。

　ここで、最小の次数が$k-1（k = \lceil \sqrt{n}\  \rceil $とする）以上になったら方針転換、k以上のサイクルを検出する方針に切り替えます。

　なぜなら、残りの点の次数が全てk-1以上なら、必ずk以上の頂点のサイクルを含むからです。ちゃんとした証明ではないけれど、その理由を以下に書きます。

　k頂点のサイクルを含まない時、一番次数を増やせるのは、k-1頂点の完全クラフです。なのでk-1頂点の完全クラフを考えると、各頂点の次数はk-2なので、各頂点からもう一個辺が出ていないといけません。そこから出る点と点が結びつけば、k以上のサイクルになるのでOK。

　そうじゃないとすると、またk-1頂点の完全グラフに結び付かなくてはいけない。だが、他の頂点からはやはりもう一個辺が出ていないといけないので……と、以下その繰り返しになるため、k以上のサイクルが存在しないとダメですね。

　で。

　サイクルの検出はDFSでOK。

　DFSで使っていない頂点をたどっていった配列$a_1, a_2,...,a_n$をしたとき、その一番最後の頂点$a_n$と繋がっているような最も最初の頂点を$a_i$として、$a_i, a_{i+1}, ... , a_n$の個数がk以上になります。

　どの頂点の次数もk-1以上という強い条件なのでこれが成り立つはず。（成り立つはずだけど、証明はよく分かっていないかも……）