Balance (CEOI 2023 Day1),Drawing (CEOI 2022 Day2),Trade (CEOI 2023 Day2) というセットをやった
A 問題の S = 2 が全ての個数が偶数ならオイラー路なのが見えて、一般化するときに S が 2 冪なので S が半分のケース 2 個に帰着したい気持ちになる。あるジャッジの問題を半分ずつに分けて、問題 k が全体で前者に配分された個数と後者に配分された個数の差を 1 以下にしたい。この問題は実質 S = 2 の問題なので解けた。かなりすんなり解けてしまい、実装も軽めで 40 分程度で 100 点を得た。
B 問題は明らかにやばいので C 問題を見ると、monge なので解けたな~と思っていたら最適な場合に選ばれる可能性のあるものの復元付きらしい。とりあえず最適解のコストだけでも 50 点は貰えるらしい。とりあえず O(NK) の dp で復元付きで 55 点を貰い、一般のケースもコストだけ答えて 80 点を貰った。ここから復元をする。最適な区間が全て分かればその個数程の計算量で復元も出来る。最適な区間が O(N) 個と大胆予想して実装してみるが TLE した。落ち着いて考えると、区間 $ \lbrack a,d \rbrackと$ \lbrack b,c \rbrackが共に最適な場合、復元の際に前者を見る必要はない。よって全体で見るべき区間数が O(N) に抑えられる。これを実装して満点を取る。(実行時間が 5000 ms などになり TL が配慮されていてよかった...)
B 問題で与えられる N 点が凸の場合は自分の子を凸包の頂点の左右に配置すればいい。一般の場合は凸包の 1 点に根を置いてその 1 点から偏角ソートをして始めの K 点を左の子に、N-K+1 点を右の子に割り振って再帰すれば O(N^2 log N) で解けそうで、選択アルゴリズムを使えば O(N^2) になりそう。準線形以降は何もわからなかった。
100 - 10 - 100 = 210 点になった。A でかなり上振れを引いたのでいつもこのパフォが出せればな...