共通の考察

大きさ \(c_1,c_2,\dots,c_s\) の団子を使って、串団子を作れる条件を考えます。これは、以下の条件に等しいです。

• 任意の整数 \(k\) について \(c\) 中の \(k\) の出現回数を \(cnt_k\) とする。\(k\) が \(c\) 中の最大値か最小値なら \(2 \times cnt_k \leq N+1\) が、そうでない場合 \(2 \times cnt_k \leq N\) が成立している。

略証として、十分性は、大きさが大きいほうから \(\lfloor \dfrac{x}{2} \rfloor\) 個、小さいほうから \(\lceil \dfrac{x}{2} \rceil\) 個並べるか、その逆をすると、適切な並び替えによって条件を達成できることがわかります。必要性について、\(2 \times cnt_k > N+1\) が成立している場合、ある \(2\) 要素が隣り合うので不可能です。\(k\) が最小値や最大値ではない場合、\(2 \times cnt_k = N+1\) の場合を考えると \(k\) が当てはまる場所は一意に定まりますが、\(k\) は最大値や最小値ではないので条件に反します。よって示されました。

また、条件に反するような \(k\) は高々 \(1\) 個であることに注意してください。

小課題1,2

順列全列挙やBit DP などを用いて valid な串団子の作り方を列挙して、DPやBit全探索などでまとめあげると良いです。

小課題3,5,6

\(dp_i\) を、前 \(i\) 項まで考えたときの答えとした dp を考えれば良いです。遷移を愚直にすると \(O(N^2)\) になるので、(最頻値を求めるところがボトルネックとなります) \(O(N^3)\) でこの問題を解くことができました。

小課題4

\(1\) と \(2\) の出現回数だけを持てば良く、最頻値が高速に求まり、\(O(N^2)\) で解けます。なお、小課題 3,4 は一番最初の条件について若干間違いがあっても通ります。(要素数が \(2\) のため)

小課題6

最頻値を高速に求める部分が問題ですが、各値の出現頻度、\(t\) 回出現するような団子の大きさの集合などを適切に管理することで、\(dp_i\) からの遷移が \(O(N)\) で可能なので、この問題を解くことができました。\(O(N^2\log N)\) 解法もありますが、定数倍が悪いと落ちる可能性があります。