2本目
Colorful Hats
N 匹が被っている帽子の色の種類数を X とする
a_i は 自分と同じ色の人がいるとき X、ユニークな色のとき X - 1 である
したがって、min(a)+ 1 < max(a) ならNo
min(a) == max(a) のとき
X = min(a), min(a)+1を両方試す
X = min(a) のとき
全ての人に対して、その人と同じ色の人がいる したがって X <= (N/2)
X = min(a) +1 のとき
全ての人がユニーク したがって X = N
min(a) + 1 == max(a) のとき X = max(a) である
min(a)の人がp人、max(a)の人がq人いるとすると(p+q == N)
p + 1 <= X <= p + (q/2)
以上で全てのケースが列挙できた
Connected?
よくあるやつで、空間をねじ曲げてよい そうすると両端店が辺上にある組以外は消える
あとはpairwiseに必ず交差する組があるかどうかを調べればよい
適当に一点で切り開いていいことが示せる（証明：がんばる）
あとは小さい側の端点を照準にソートして
N種のカッコ列と考えてstackで処理する、setでやる、priority_queueでやる お好きにどうぞ
guruguru
全ての位置に対して尺取りなりimosなりで答えを求める
頑張って1周のまま尺取りしたら無限にバグった
円環切るんだから明らかに3周させるべきなんだよね
感想
今タイムスリップしたら赤パフォ出しまくり勝ちまくりだな（詠嘆）
