CodeIQというところでプログラミング問題「ループ・トラッキング」に解答しましたので、ネタバレです。

問題

今回は次のような問題でした。

整数関数 $F_n(x)$ を、$F_n(x)=\lfloor \frac{4x(n-x)}{n}\rfloor\,\,(0\le x \le n)$ で定義する。
この時、$F_n(x)$ の値もまた、$0$以上$n$以下になることが分かります。なので、$k\rightarrow F_n(k)$ という変換を繰り返すと、いつか重複した値が現れ、そこから先はループになります。
そこで、関数 $G(n,k)$を、上記の変換を繰り返した時に既出の値が出現するまでの回数と定義する
例えば、$n=10$の時、$F_n(1)=3,\,F_n(3)=8,\,F_n(8)=6,\,F_n(6)=9,\,F_n(9)=3$ と5回で3が重複のため、$G(10,1)=5$です。
入力される自然数 $n\,(1\le n\le 3\cdot 10^{5})$ に対し、$G(n,k)$の総和 $H(n)=\sum_{k=0}^{n}G(n,k)$ を計算し、出力する

解説

ということでどう解くかですが、「回数」を直接的にかつ効率よく求める方法が思い浮かびません。そこで、$k\rightarrow F_n(k)$ を、ノード 0～$n$ から構成される有向グラフ上のパスと見做し、グラフ探索を考えることにしました。

以下、$n=8$の例で説明していきます。

グラフの構成
ということで、構成した有向グラフは次の図のようになります。

しかしこの問題では、各ノードを起点としたループに辿りつくまでのパス数を数える必要があります。つまり、各パスで多重度を見る必要があるということです。反映すると次の図のようになります。多重度込みでパスを数えると19本、つまり$H(8)=19$ということになります。
方針と初期状態
では多重度をどのように考えるか、これをパスではなくノードに対して「重み」パラメータwを付与することで対処します。
そしてグラフの端 ( 接続元がないノード ) から順にノードを取り外す ( グラフから削除する ) 過程でパスを数えていくことを考えます。そのため、接続元ノード数を表すパラメータsも用意します。w,sを反映した初期状態は次の通りです。
端のノードの取り外しとパラメータ更新
ではまず、端になっているノード1,2,4,5を取り外します。端になっているかどうかは、各ノードのsパラメータが0であるかどうかで判断できます。そしてこの時、各ノードから伸びていて、取り外しによってなくなる計4本のパスを答えに計上しておきます。
取り外すと同時に、ノードが持っていたwパラメータを接続先ノードに委譲 ( 要は加算 ) するのと、ノードが消えた分のsの減少を反映します。

こうして、改めて 8 が端になりましたから、次はこれを取り外します。こんどなくなるパスは、wパラメータの値 ( の合計 ) そのものです。つまり、2本のパスを計上します。
最終形とループ分の形状こうして端をどんどん取り外していくと、純粋にループとなっている部分のみが残ることになります。そのため、後はループに含まれるパス数を計上すれば最終的な答えになります。
それぞれの独立したループに対して、パス数は(wの合計)×(ループ長)となっていますから、順々にループを辿っていけば良い、ということが分かります。