解説 - AtCoder Regular Contest 154

公式

コンテスト全体の解説 by PCTprobability

ヒント集

ヒント 1

\(N=2\) のときを考えてみましょう。

ヒント 2

\(A \times B\) をいくつかの \((10^ix+y)(10^iz+w)\) に分解します。

ヒント 1

\(S,T\) をソートした文字列が一致していることが \(S,T\) を操作で一致させるための必要条件です。

ヒント 2

もし \(S,T\) を一致させられるならば、\(N-1\) 回の操作で必ず一致させることができます。何故でしょう？

ヒント 1

\(A=(1,2,\dots,N)\) の時を考えましょう。

ヒント 2

\(1\) 回でも操作をすると、\(A\) に出てくる整数の種類数は \(N-1\) 種類以下になります。

ヒント 3

\(1\) 回でも操作すると、\(A\) を自由に rotate させることができます。

ヒント 1

\(P_i = 1\) を満たす \(i\) を求めましょう。

ヒント 2

あるソートアルゴリズムを利用します。

ヒント 3

相異なる整数 \(a,b\) に対して \(a+1 > b\) と \(a > b\) は同値です。

ヒント 1

\(f(P) = \sum_{i=1}^{N} i(i-P_i)\) が成り立ちます。

ヒント 2

操作によって \(1\) 回でも反転対称になった要素について、ある事実が成り立ちます。

ヒント 3

その事実とは、位置の分布が左右対称になることです。

ヒント 1

\(i\) 回操作したときに全ての出目が出ている確率母関数の EGF を求めます。

ヒント 2

求めた EGF を OGF に変換します。

ヒント 3

確率母関数 \(f(x)\) に対して、\([x^k]f(e^x)\) がどのような値かを求めてみましょう。