ACPCVC20200518 復習メモ - tinumu's reminder

かなり遅れました。全部書きたいです。

A - ConvexScore

ある $S$ のスコアは $2^{n-|S|}$ であるが、これは内包されている点たちの集合を $T_s$ と置いた時にその部分集合の個数と一致する。
ここで、ある凸多角形を決めたときに、その内部のパターン数を求めて、全ての凸多角形に対して数え上げれば良いという問題①に落ちる。
ここで、 $3$ 点以上からなる凸包の面積が正になっているような点の集合の個数を全て数え上げるとする。
すると、それぞれの集合に対して凸包が一意に定まっているし、全ての凸包を網羅するので、①の答えになっている。

そのため、すべての点集合の個数 $2^N$ から、空集合、 $1$ 点しか無い集合、 $2$ 点以上の直線になっているものの集合の個数を引いてあげれば答えが出るということになる。

空集合の個数は $1$ , $1$ 点しか無い集合の個数は $N$ である。
$2$ 点以上の直線になっているものの集合の個数は、それぞれの直線で考えていくが、ある直線上に $k$ 点乗っている場合、それらの $2$ 点以上の集合の個数は $2^k - k - 1$ となっているので、それぞれの直線に対して $\mathrm{O}(N^3)$ で計算してあげると、最終的な答えが求まる。

スコアの性質をうまく使わないと解けない問題だった。

B - Bichrome Tree

ある部分木 $T$ があって、その根を $v$ としたときに、その $T$ の持つ重みの和がどちらかが $X_v$ , もうひとつが何らかの値 $val$ みたいになる(白黒は関係なくて、どっちの色でも $(X_v, val)$ のペアは達成できる)。この $val$ を最小化しておけば、 $T$ より大きい部分木に対して一番有利に働くだろう。
そこで、
$dp_v$ … 根 $v$ の部分木について、自分の色じゃない方の重み $val$ の最小値
と置く。これに対する漸化式が求まれば、 $dp_1$ の値が存在するか否かで作成可能かそうでないかが分かるはずである。

ここで、ある部分木の根を $u$ , $u$ の子を $v$ とする。
$v$ たちはそれぞれ、 $X_v$ , $dp_v$ の値を持っているが、どちらかを $X_u$ を構成する重みに割り振るか、そうでない方に割り振るかという選択を行うことが出来る。
すべて選択した後、重みの和が $X_u$ 以下(頂点 $v$ 自体も重みを割り振れるので $X_u$ になるように帳尻合わせが出来る) になっているものに対して、もうひとつの値 $val$ が一番小さいものを選べばいいということになる。
とすると、これも DP を用いて解くことが出来る。
$dp2_{v,j}$ ... 現在頂点 $v$ まで見た時に $X_u$ を構成する重みが現在 $j$ になっているときの、もうひとつの値の最小値
これを使うと、 $dp_u = \mathrm{argmin}_{1 \leq j \leq X_u} dp2_{n, j}$ とすることができるので $dp_u$ の漸化式が求まった。
$n$ は頂点 $u$ の子の数とする。

３重ループになるから一見間に合わなそうだが、辺の数は $N-1$ しか無いので $\mathrm{O}(N^2)$ になっている。

C - Four Coloring

これはグリッドを $45$ 度回転すると、ある点 $p$ から距離が $d/\sqrt{2}$ であるような点は $p$ を中心とした正方形を描くことになる。
この条件でやると、どうやら、 $1$ 辺 $d/\sqrt{2}$ の正方形を敷き詰めてもその正方形の点同士は条件を壊さない。
周辺が危険になっているので、他の色の正方形を敷き詰めることを考えていくと、
赤青赤青　 $\cdots$
黄緑黄緑
赤青赤青
黄緑黄緑　 $\cdots$
$\vdots$

みたいにすると、何一つ条件を壊さないようなので、このまま $45$ 度回転して元の座標に戻すとOK

感想

直感的にCのほうがBよりdiff高いのなんか違和感がある
Aみたいな問題は考察を間違えると、かなりドツボにはまりそう。　全然わからなかったら一回リセットして考え直してみるといいかも知れない。

反省

面白くない駄文ですが書きます。
競プロの時間を減らして色々なことに手を付けているつもりだったんですが、やっぱりつもりだったようです。考えてみれば何も達成してないのに他のことをやる意味がなかったです。今の所、学業と競プロをやり続けなければ、自分に何の価値も無いようなので頑張ります。　
このまま、社会性も実力もないのでは、将来大したこと無い事をしているヤバイおっさんに成り果てそう