C - Exception Handling

逆元を持たない演算 $+$ に対し $f(a) = \sum (A \setminus { a })$ をたくさん求める問題。 これぐらいまでは機械的な式変形で解けたい。

D - Preparing Boxes

後ろから順に決めていけば常に構築できる。 $O(n^2)$ ぽいが調和級数の和にできて $O(n \log n)$。

E - Sequence Decomposing

愚直な貪欲、つまり最長増加部分列を作ることを繰り返すことをすると $O(n^2 \log n)$ になる。 これを並列に行うと $O(n \log n)$ になる。 つまり構築途中の LIS の末尾 (あるいは先頭) の数の多重集合を持っておいて貪欲に伸ばしていく。

これはひとつの最長減少部分列を作ることに等しい。 これは Dilworth’s theorem 「antichain の長さの最大値は chains への分解の大きさの最小値に等しい」の適用例そのものになっている。 最長増加部分列とは $(i, a_i) R (j, a_j) \iff i \lt j \land a_i \lt a_j$ で定義される半順序の上での chain であり、最長減少部分列とは antichain である。

F - Permutation Oddness

置換 $\sigma \in \mathfrak{S} _ n$ であって $\sum |\sigma(i) - i| = k$ なものの数を数える問題。 置換 $\sigma$ の値 $\sigma(0), \sigma(1), \dots$ を順番にと構成していくような DP をする。 $(i, \sigma(i)) \in \sigma$ を区間 $[i, \sigma(i)]$ (あるいは区間 $[\sigma(i), i]$) であるように考え「左端は決まったが右端はまだ決まってない区間の数」「右端は決まったが左端はまだ決まってない区間の数」を持つ系の典型 (箱根DPとか箱根駅伝DPと呼ばれてるぽい) をやる。 すると $O(n^2k)$ になって解ける。

置換 (あるいは順列) は関数であり、そのグラフを考えれば $n = { 0, 1, \dots, n - 1 }$ と $n = { 0, 1, \dots, n - 1 }$ の間のマッチングである。 その左右を気にしなくてよいならば区間の集合であるとみなせ、区間属性のテクが利用できるようになる。 「置換の構成はそのグラフを区間の集合と見る」は典型として記憶しておきたい。

OEIS もできたらしい。二次元の数列だったので諦めてしまったが、雑に繋げて投げれば引っかかるようだ。これも典型とのこと。

反省

  • D で調和級数という言葉がすぐ出てこなかった。
  • E の multiset 解が、前からでも後ろからでもよいことに気付いてなかった。LIS の計算量を $O(n)$ と勘違いしてた。Dilworth’s theorem を知らなかった
  • F に 70 分かかった。ひとつ TLE を生やした。OEIS を試したが見つけられなかった。

リンク