A が簡単枠に見えたのでとりあえずやってみる。k/a + k/b の意味がよく分からないがとりあえず i 個買ったときに x_i 個貰えるとして、買う個数を固定する。価値の順番に降順ソートすると始めの k 個からは買う or 貰う、後ろの n-k 個からは買う or 貰わないとなるため、その境界と買ったものの値段の総和と買うものの個数を全探索することが出来る。予め適切な dp をしておけば O(N^2M) となる。30 分程で 100 点を得た。(結局 k/a + k/b の意味は何だったのだろう...)
B と C を見る。C はやばそうなのでとりあえず B を考えてみる。二分探索をすることを考えると、x 以下のものの個数は境界をなぞるように見ることで 2N 回のクエリで求められる。なので二分探索をしてみると 55.49 点が得られる。何故かかなり高い点数になっていて、よく見てみると聞いたところがかなり被っているらしい。ここから二分探索をするときに、$ l=0,r=n^2,ok=0,ng=10^{18}から始めて二分探索をしていくが、$ midを平均値にするのではなく、$ mid = ok + (ng-ok) (k-l)/(r-l+1)にする。つまりランダムに分布するときの k 番目の値の期待値にセットする。このままだと$ r-lが大きすぎるときなどに死ぬので常に$ r-lが 3% は小さくなるようにする。するとかなり点数が上がり 76.72 点が得られた。
パラメーターを色々変えても点数が上がらなかったので C を見る。とりあえず小課題 1 は簡単だったので取る。小課題 3 も頂点 1 からの距離が最も遠いものがパスの端点なので、それを利用するとグラフの全貌が得られる。後は適当に stack 等で処理すればよい。他の小課題を考えるが、そもそも全ての頂点が深さ 1 or 2 で、深さ 1,2 の頂点間が完全マッチングのようになっている場合木の特定が不可能であることに気付きかなり分からなくなってしまった。諦めて B に戻る。
B に戻ってくる。小課題 4 で満点でないケースが 1 ケースのみだったので、適当に ok-ng に 0.95 や 1.05 をかけるなどをして満点を狙ってみると小課題 4 が満点になり 78.65 点が得られた。あとは初期値を$ ok=ask(1,1)-1,ng=ask(n,n)にするなどをして点数を伸ばし最終的に 81.6 点になった。
結果は 100-81.6-33 = 214.6 点となった。B の満点を読むと (n,n) のケースを (n,n/2) のケースを利用して再帰する解法で、この考え方は頭に入れておこうとなった。C の解説はまだ理解できていない...