AtCoder AHC044 \(O(N ^ 3)\) 解法
4msで動作した本番69位の解法を紹介します。 問題リンク https://atcoder.jp/contests/ahc044/tasks/ahc044_a 解説 何人かの社員を選んで一列に並べ、社員を頂点、次の割り振りへの遷移を辺としたグラフを考えます。簡単なグラフをいくつか作って挙動を確かめてみると、次のようにして構築できるグラフの性質がよさそうなことがわかりました。 割り当て回数が偶数のとき（画像橙線）、次は右隣の人に割り当てる ただし右端からは左端を割り当てる 割り当て回数が奇数のとき（画像青線）、次は左隣の人に割り当てる ただし左端からは右隣を割り当てる 左端から始めてこのグラフを一周するまでにそれぞれの頂点を訪れる回数は、頂点数を\(k\)とするとき、左から\(k, 2k - 2, 2k - 4, 2k - 6 ... , 6, 4, 2\)となります。右端の頂点を訪れる回数を基準に、その1倍、2倍、3倍、……、k - 1倍の回数だけ訪れる頂点を作れるので、 各社員の割り当て回数の目標が一様ランダムであることを考えると、問題をこのグラフに帰着させることでそこそこよさそうな割り当てが得られそうだと感じられます。 実際にこのグラフ（以下、元のグラフ）にすべての社員を当てはめる際には、ひとつの頂点に複数の社員を対応させたくなります。次のように構築する（以下、割り当てグラフ）ことで、同じ回数だけ訪れる複数の頂点を並べることができます。 割り当てグラフにおいて、\(L\)回目の頂点を訪れるまでにある頂点を訪れる回数は、\(\frac{Lkv}{SN}\)と見積もれます（元のグラフにおいて一周するまでに訪れる頂点の合計を\(S\)、選んだ頂点に対応する元のグラフの頂点を一周するまでに訪れる回数を\(v\)とする）。元のグラフのひとつの頂点に対応させる社員の数がおよそ\(N/k\)であることを用いています。 \(k\)を\(N\)まで試し、それぞれの社員について割り当て回数が上記の見積もり回数に一番近い頂点に当てはめることで、割り当てグラフを構築できます。実装上、元のグラフの頂点に最低一人の社員を当てはめるようにする必要があります。スコアの評価も見積もった値か...