2019-12-14
■ 冬休み1日目
2018-2019 ACM-ICPC, Asia Xuzhou Regional Contest
AGHILMを解いた。
I
LIS長がN-1の順列はそう多くはないので、それぞれを生成するような順列を直接数える。
勿論、swapが起きる所を辺で繋いだ時の連結成分ごとに考えれば良く、これは前から見る(順列全生成)と絶対間に合わないが、後ろから見る(いい感じに探索)と間に合う
M
各々の光源がどこからどこまでを照らせるかわかれば解ける。
そのためには必ず照らせる頂点を求めて、両方向に伸ばしていけば良いが、前者はユークリッド距離が一番近い点、後者はccwだけで判定可能。見た目は幾何だけど幾何ではない
L
acyclic olientationは(-1)^N * P(G,-1)で数えられるので、結局彩色多項式の一点評価ができればよい。
N <= 36なので、色が高々37種類存在する時の塗り分け方を数えれば良く、これは面倒なDPをやればできるんですが、バグります
DとJはまともに難しいので後でちゃんと解く
Codeforces Round #604 (Div. 1)
ABCを(信じられないほど遅く)解いた。
Dはまともに難しいので後でちゃんと解く
明日大事なコンテストなので早寝
