Codeforces Round 1100
F問題の $ O(N 2^N) 解法が面白い。
問題
長さ N の数列 A が与えられる。
自由に並び替え、K 個の 0 からなる数列 B に対して以下の操作を行う。
最小の要素に $ A_i を足す
max(B) の最大値は？
前提考察
max(B) が最後に更新されるタイミングを考える。
「その時点でのmin(B)」+$ A_i になる
これは最後だとして良い。
そうでないなら、更新後に追加するものを i の直前に持ってきて良い
min(B) は単調増加なので
min(B) の最大値を求める際は「B の好きな要素に$ A_iを足す」だと思っても良い。
$ B_i に足される集合を $ S_i とする
任意の$ x \in S_iに対して$ B_i - x \le min(B)が成り立つ最適解が存在するため、操作列も存在
そうでないなら$ xを i から j に移せば min を減らさずに分散を減少させられる
最後に足す要素は max(A) だけ試せば良い。
そうでないなら、max(A) と swap することで答えが減らない
操作実現性については前述の通り無視して良い
本質パート
N 個の整数を K 個の箱に分ける。min(箱内の和) の最大値は？
二分探索してdp、より計算量を落として下さい
dp: 1 個ずつ追加していき、和が目標値を超えたら次の箱にする
dp[追加した集合]= (完成した箱の個数, 今の箱内の和) の max
本質考察
「今の箱内の和 * 残り箱数 ≧ 残りの和」を満たし次第、次の箱に行く
min(箱内の和) が必ず最後の箱になる
どのような分け方もカバーできている（この条件を満たす箱の順番が存在する）
具体的には、箱内の和の降順
/icons/hr.icon
参加した。21位。PCカバーとストレス解消グッズがもらえるっぽい？やったー
A 両端に注目
B 最小化だと誤読し、もたもた
C 後ろから操作しよう
D
二分探索
隣接に「aa→a」「bb→b」「ab→」「ba→」をして、b だけを残せるか
aa をやってから b > a ならよい（ba をやったら新たに aa が出来る、なんてことは起きない）
E
N を根とする
葉は単調増加
「頂点 v を採用するためには、直前は x 以上でないといけない」という条件で dp
F
二分探索＋最後の要素を試す＋dpの$ O(N^3 2^N) を枝刈った
最後はmaxが強そうだと思いつつも、単純に交換するだけでは操作列が壊れるから怪しく思ってしまった
二分探索：和の候補 $ 2^N 通りを列挙してからそれを二分探索
枝刈り：最後の要素は大きい順に試し、答えを更新できる範囲でしか二分探索をしないようにした
（多分結局 $ O(N^2 2^N) になってそう？）
計算量区別不可能でお祈りゲーになってそうだが、$ O(N 2^N)が面白すぎるので結果的に良問に。
G
開店凸が最善。やるだけ。
CHTは区間クエリ不要。
Fで集中力消滅、式を詰めるのに無限時間。
H
判定問題を考えるとdpが出来そうだが、式を詰めるのが間に合わない。