AtCoder Beginner Contest 134
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 である。
Dilworth's theoremで検索してください。
— やる:賃貸更新、自転車保険、ラッシー作る 買う:ヨーグルト、非遮光カーテン (@potetisensei) July 20, 2019
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 もできたらしい。二次元の数列だったので諦めてしまったが、雑に繋げて投げれば引っかかるようだ。これも典型とのこと。
OEISでT(n, k)型の数列を1列に並べて調べるのも典型テクなんですよね~
— satanic@競プロ🔥 (@satanic0258) July 20, 2019
反省
- D で調和級数という言葉がすぐ出てこなかった。
- E の
multiset
解が、前からでも後ろからでもよいことに気付いてなかった。LIS の計算量を $O(n)$ と勘違いしてた。Dilworth’s theorem を知らなかった - F に 70 分かかった。ひとつ TLE を生やした。OEIS を試したが見つけられなかった。
リンク
- https://atcoder.jp/contests/abc134/
- D: https://atcoder.jp/contests/abc134/submissions/6456947
- E: https://atcoder.jp/contests/abc134/submissions/6459386
- F: https://atcoder.jp/contests/abc134/submissions/6474168
- Dilworth’s theorem https://en.wikipedia.org/wiki/Dilworth%27s_theorem
- F の OEIS https://oeis.org/A062869
- 箱根駅伝 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2439
- 箱根駅伝 解説 http://jag-icpc.org/index.php?plugin=attach&pcmd=open&file=3A-F.pdf&refer=2012%2FPractice%2F%E5%A4%8F%E5%90%88%E5%AE%BF%2F%E8%AC%9B%E8%A9%95