CSAcademy 13

Dominant Point

x 座標最大の点が解の候補である。この候補が dominates するかをチェックしよう。

Pokemon Fight

小さい値を貪欲にペアにすれば OK。

Balanced Min Pairing

ソートして、a[0..n/2) と b[n/2..n)、 a[n/2..n) と b[0..n/2) をペアにする。a[i] を勝たせたいなら、勝つ相手が小さい値であったほうが a[j] を負けさせるときの選択肢が広がるので良い。また半分より大きい値は勝ちに行かせた方がいい、ということを考えるとこのようなペア組が最適であることが分かる。

Num Cube Sets

正規化すると話が簡単になる。正規化というのは、a[i] が立方数を因数に持たないように立方数でできるだけ割る操作を表す。このようにすると a[i] と掛けて立方数になるような数は一意に定まる。

正規化した値とペアになる値をエラトステネスの篩の要領で前計算しておくことにより、全体の計算量は O(A log log A +N+M) となる。

And Closure

1 から 2²⁰ の値を構成できるかを順に判定する。判定は O(20) 程度で済ませたい。

dp[100101] := 1..1.1 の形の要素がいくつあるかとする。これは部分集合に対して伝搬させる高速ゼータ変換により O(20 2²⁰) で計算できる（仰々しい名前だけどやってることは bitDP）。

100101 が作れるかを判定する際は、10.1.1, 1.01.1,1..101 がそれぞれ存在するかどうかを判定すればいい。10.1.1 であるような要素の数は dp[11.1.1]-dp[1..1.1] で計算できる。

Interval Expected Max

O(10⁵×500×log 10⁶) で通した。3081 ms。

期待値=sum(a[i] × i番目の要素が最大になるパターン数)/（要素数)^2 で計算できる。ただし (i番目の要素）＞（j番目の要素）は (a[i],i)>(a[j],j)であるものとする。 分割統治っぽいことは難しそうなので、Mo's algorithm で処理しよう。現在の区間から 1 つ広げるときに、「a[k] より小さい要素の個数」と「a[k]より小さい要素の総和」があると良いので BIT を 2 つ使う。

E が解けず残念な結果になってしまった。