AtCoder Beginner Contest 284 E,F,G問題メモ

AtCoder Beginner Contest 284

E - Count Simple Paths

• $N$ 頂点 $M$ 辺の単純無向グラフが与えられる
• 頂点 $1$ から始まる単純パス（同じ頂点を複数回通らないパス）の個数を求めよ
  • 長さや終点は問わない
  • ただし $10^6$ を超える場合は $10^6$ と出力する
• $1 \le N \le 2 \times 10^5$
• $0 \le M \le 2 \times 10^5$
• 各頂点の次数は10を超えない

一度調べた頂点でも、一旦戻って、別のパスから到達したときはまた調べる、というようなDFS。

一般的にDFSでは、一度訪れた頂点は再度訪れないように何かしらの記録をつけるが、今回はそれを帰りがけ時に未探索に戻すとよい。

深い再帰はPythonや、特にPyPyでは遅くなるので、警戒が必要。
可能なら非再帰で実装すると安心。まぁ概して再帰より書きづらいことが多いが。

次数の制約が最初よくわからんかったが、たしかに、これが無いとTLEケースを作れてしまう。

10万個のパスを見つけたら打ち切れるとはいっても、 「探索先は既に訪れているので答えにはカウントされない」ケースもあるので、 実際の探索は10万回以上になり得る。

①から9900頂点くらい1本道が続き、その先に100頂点くらいの完全グラフがあり、 その10000頂点全てに接続する頂点が10点くらいあるグラフを考える。

①--②--③-- .. -(9900)--(100頂点の完全グラフ)
    |\   \        /      //////////////////
    \ `----- X --------------------------'
     `------ Y ------------------------'

仮に、探索順で運悪く、上側の10000頂点全てに訪れてからXに訪れたとする。
この時点でパスは約10000通りで、打ち切るにはまだまだ足りない。

Xから調べる頂点は全て探索済みなので、10000回の探索が無駄になる。
1つ戻って次にYに訪れ、同様に10000回が無駄になる。
このような頂点が10点あると、計100000回の探索が無駄になる。ここまでで新規パスは10個しか増えていない。

ちょっと完全グラフを戻って、少しだけ違うパスでまた同様のことが起こると、 新規パスは10くらいずつしか増えないのに、探索は100000の係数で増えていく。

結果、TLEとなる。

無駄な探索が少なくなるように最初の10万パスが見つかればよいが、 どこを先に探索すれば良いかを簡単に事前に知る方法もない（と思う）ので、運次第でアウトとなる。

う～ん、次数の大きな頂点を優先的に調べるとかで意外と回避できたりするのか？
上の例はXやYを先に探索すればこのようなケースを回避できるが、どこを先に探索してもダメなケースは制約内で作れるのか？
この辺はちょっとわからない。

Python3

F - ABCBAC

• 長さ $2N$ の文字列 $T$ が与えられる
• $T$ は、長さ $N$ の何らかの文字列 $S$ に対して、以下の操作を行った結果である可能性がある
  • $S$ を $i$ 番目の文字で2つに区切る
  • 「区切った左側」「$S$ を反転させたもの」「区切った右側」をこの順に並べる
• 元の文字列 $S$ と区切り位置 $i$ を求めよ。不可能な場合は報告せよ
• $1 \le N \le 10^6$

まず $T$ の構成を考える。
$S$ を2つに区切ったのを [ L ], [ R ] とすると、反転させたものは [ Я ][ ᒧ ] なので、

[ Ｌ ][ Я ][ ᒧ ][ Ｒ ]

反転させても長さは等しいため、前半と後半の長さは等しく、半分で分ければ綺麗に2つずつのブロックになる。

①後半部を反転させてみる。

[ Ｌ ][ Я ][ Я ][ Ｌ ]

すると、[ Ｌ ] が先頭と末尾に共通して現れるので、 Z-Algorhithmを使えば、（Яはわからないが）Ｌに関しては一致するような区切り位置が $O(N)$ で列挙できる。

• 文字列の頭良い感じの線形アルゴリズムたち３ - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
• 【図解】線形時間の文字列アルゴリズム「Z algorithm」をイラストとアニメーションでかみ砕く - Qiita

また、②前半部を反転させると

[ Ｒ ][ ᒧ ][ ᒧ ][ Ｒ ]

今度は [ Ｒ ] に対して同様のことがわかる。

①で位置 $i$ で区切ることが可能だったとして、 ②でも同じ位置で（[ Ｒ ]の長さが $N-i$ になるように）区切ることが可能であれば、そこが答え。

Python3

G - Only Once

公式解説 の<参考>にしたがって、グラフの問題に言い換え

• 各要素が $1～N$ である長さ $N$ の整数列 $A=(A_1,...,A_N)$ に対して、以下の問題を考える
  • $N$ 頂点の、$i→A_i$ に有向辺を張ったグラフを作る
  • 頂点 $i$ から辺にしたがって移動を繰り返す（行き先は必ず1通り）
  • $i$ を始点として無限に移動を繰り返したとき、1度しか通らない頂点数を $S_i$ とする
  • 全ての頂点に対する $S_i$ の総和を $T$ とする
• $A$ として考えられる整数列は $N^N$ 個あるが、全てに対しての $T$ の総和を、$M$ で割った値で求めよ
• $1 \le N \le 2 \times 10^5$

必要なのは、主客転倒の考え方と、状態を上手くまとめられるような「固定する値」の決め方。
特に後者は、なかなか自力では思いつきづらそうに感じる。

上記の言い換えのように、各頂点から1本ずつ有向辺が出ているグラフを Functional Graph という。

• My Algorithm : kopricky アルゴリズムライブラリ

Functional Graphは、連結成分につき、1つのループに、ループ上の頂点を根とする木がいくつかくっついた形となる。木の辺は葉から根に向かう。

よってその上で移動を繰り返すと、どこかから（または最初から）同じ頂点群をぐるぐるループすることとなる。

ループするまでに通過する、木に属する部分の頂点数が各 $S_i$ となる。

頂点 $i$ 毎に「$S_i=0$ となるような $A$ は何個、$S_i=1$ となるようなのは何個、、、」というのを考えれば、 その頂点が最終的な答えに寄与する量 $c_i$ がわかる。答えは、全ての頂点に対する $c_i$ の総和とも表現できる。

で、どの頂点も性質に違いは無いので、$c_1=c_2=...=c_N$ であり、1つの頂点について求めれば、答えは $N$ 倍すればよいとわかる。

• あの〜、お詫びと言っては何ですけどちょっと数え上げでよく見るらしい「主客転倒」の解説今から書くんで… - physics0523's 精進ログ

よって、頂点1についての $c_1$ を求めることにする。

だが、これもなかなかアプローチがつかみづらい。

$S_1=0$ は無視して良いとして、$S_1=1$ ならループする頂点の個数を決めればどこにつなげるかで求められそうだが、 $S_1 \ge 2$ になるためにはそれより前に踏み台が必要なので、踏み台が何個のケースが何通りで……などと考えると、$O(N)$ では無理に見えてくる。

$S_1$ の値ごとに場合の数を考えるアプローチから、一旦離れる。

ここは、$1$ から頂点を辿っていったときに「ループまで＋ループ1周分」の頂点数 $L$ を固定すると、綺麗にまとめられる。
なかなか変則的にも見えるが、まぁ、「1から実際に通過する頂点たち」と考えれば妥当な気もしてくる。

この $L$ 個の部分の場合の数は、始点は1固定なので、残り $L-1$ 個の通過順で、${}_{N-1}P_{L-1}$ 通り

通過順を決めると、$A$ のうち、$A_1, A_{A_1},...$ の $L-1$ 個の値が1対1対応で決まる。

そして最後の $L$ 個目の行き先は、ループするので、自身を含めた $L$ 個のうちのどれか。

                       L個目
①→○→○→ ... →○→○┐
↑  ↑  ↑         ↑  ↑｜  どこに戻る?
 - - - - - - - - - - - - ┘

$P$ 個目に戻った場合、答えに寄与する頂点数は $P-1$ 個。
なので、$P=1～L$ まで動かした場合、その和は $0+1+2+...+L-1=\dfrac{L(L-1)}{2}$ となる。

最後に、$L$ 個以外の $A_i$ はどう決めても①からの遷移に影響しないので、自由に決められる。$N^{N-L}$ 通り。

これらを掛け合わせることで、$c_1$ が求められる。

• $\displaystyle \sum^{N}_{L=1}{}_{N-1}P_{L-1} \times \frac{L(L-1)}{2} \times N^{N-L}$

Python3